本文主要是介绍To the moon HDU - 4348，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
主席树区间更新模板
对于主席树中的每一颗线段树 除了左右区间的位置与父区间不再有任何关系以外 其他都是一模一样
但是因为主席树中的线段树每一个区间和左右子区间的关系不好找 只能pushup 不能pushdown
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long longstruct node
{int nl;int nr;ll val;ll laz;
};node tree[2500010];
int root[100010];
int n,num,now;int build(int l,int r)
{int m,cur;cur=num++;tree[cur].nl=0,tree[cur].nr=0;tree[cur].val=0,tree[cur].laz=0;if(l==r){scanf("%lld",&tree[cur].val);return cur;}m=(l+r)/2;tree[cur].nl=build(l,m);tree[cur].nr=build(m+1,r);tree[cur].val=tree[tree[cur].nl].val+tree[tree[cur].nr].val;return cur;
}int update(int rot,int pl,int pr,ll val,int l,int r)
{int m,cur;cur=num++;tree[cur]=tree[rot];tree[cur].val+=val*(min(pr,r)-max(pl,l)+1);if(pl<=l&&r<=pr){tree[cur].laz+=val;return cur;}m=(l+r)/2;if(pl<=m) tree[cur].nl=update(tree[cur].nl,pl,pr,val,l,m);if(pr>m) tree[cur].nr=update(tree[cur].nr,pl,pr,val,m+1,r);return cur;
}ll query(int cur,int pl,int pr,int l,int r)
{ll res;int m;if(pl<=l&&r<=pr){return tree[cur].val;}res=tree[cur].laz*(min(pr,r)-max(pl,l)+1);m=(l+r)/2;if(pl<=m) res+=query(tree[cur].nl,pl,pr,l,m);if(pr>m) res+=query(tree[cur].nr,pl,pr,m+1,r);return res;
}int main()
{ll val;int q,flag,l,r,t;char ch[10];flag=0;while(scanf("%d%d",&n,&q)!=EOF){if(flag) printf("\n");else flag=1;memset(tree,0,sizeof(tree));memset(root,0,sizeof(root));num=0,now=0;root[now]=build(1,n);while(q--){scanf("%s",ch);if(ch[0]=='C'){scanf("%d%d%lld",&l,&r,&val);now++;root[now]=update(root[now-1],l,r,val,1,n);}else if(ch[0]=='Q'){scanf("%d%d",&l,&r);printf("%lld\n",query(root[now],l,r,1,n));}else if(ch[0]=='H'){scanf("%d%d%d",&l,&r,&t);printf("%lld\n",query(root[t],l,r,1,n));}else{scanf("%d",&now);}}}return 0;
}
这篇关于To the moon HDU - 4348的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
