POJ - 3468 线段树区间修改，区间求和
由于是区间求和，因此我们在更新某个节点的时候，需要往上更新节点信息，也就有了tree[root].val=tree[L(root)].val+tree[R(root)].val;
但是我们为了把懒标记打上，当节点表示的区间是完全被询问区间包含，那么这个区间的信息都是有用的，因此我们其实只需要把这个节点更新，并打上懒标记即可。如果以后update 或者 query 需要跑到下面，直接往下pushdown即可。
pushdown的时候，由于当前层的信息已经更新，我们需要把信息往下推，并把子节点的信息维护，因此需要把laze标记往下打，并且往下更新修改即可
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int maxn = 100003; long long sum; inline int L(int r) { return r<<1; } inline int R(int r) { return r<<1|1; } inline int MID(int l,int r) { return (l+r)>>1; } struct node { int left,right; long long val,add; } tree[maxn<<2]; long long b[maxn]; void pushdown(int root) { if (tree[root].add) //这个节点内部需要往下更新 { tree[L(root)].add+=tree[root].add;//把laze标记往下传递 以后再进行更深的节点 tree[R(root)].add+=tree[root].add; tree[L(root)].val+=(tree[L(root)].right-tree[L(root)].left+1)*tree[root].add;//laze标记应该标记在自己的本身的位置 去改变下一个位置 tree[R(root)].val+=(tree[R(root)].right-tree[R(root)].left+1)*tree[root].add; tree[root].add=0;//消除标记 } } void buildtree(int root,int l,int r) { tree[root].left=l; tree[root].right=r; tree[root].add=0; if(l==r) { tree[root].val=b[l]; return; } int mid=MID(l,r); buildtree(L(root),l,mid); buildtree(R(root),mid+1,r); tree[root].val=tree[L(root)].val+tree[R(root)].val; } void update(int root,int l,int r,long long v) { if(l<=tree[root].left && tree[root].right<=r)//包含在询问的区间内部 { tree[root].add+=v;//打上标记 tree[root].val+=v*(tree[root].right-tree[root].left+1);//修改 return; } pushdown(root); if(tree[root].left==tree[root].right) { return; } int mid=MID(tree[root].left,tree[root].right); if(l>mid) update(R(root),l,r,v);//左区区间仅仅在右儿子节点中 else if (r<=mid)update(L(root),l,r,v);//仅仅在左儿子节点中 else { update(L(root),l,mid,v);//继续向下询问 update(R(root),mid+1,r,v);//继续向下询问 } tree[root].val=tree[L(root)].val+tree[R(root)].val;//把更新往上修改 } void query(int root,int l,int r) { if (l<=tree[root].left && tree[root].right<=r) { sum+=tree[root].val; return; } pushdown(root); if(tree[root].left==tree[root].right)return; int mid=MID(tree[root].left,tree[root].right); if (l>mid)query(R(root),l,r); else if (r<=mid)query(L(root),l,r); else { query(L(root),l,mid); query(R(root),mid+1,r); } } int main() { int n,m; char op; int tmp1,tmp2; long long tmp3; while(~scanf("%d%d",&n,&m)) { for (int i=1; i<=n; i++) { scanf("%lld",&b[i]); } buildtree(1,1,n); while(m--) { scanf(" %c",&op); if (op=='Q') { scanf("%d%d",&tmp1,&tmp2); sum=0; query(1,tmp1,tmp2); printf("%lld\n",sum); } else { scanf("%d%d%lld",&tmp1,&tmp2,&tmp3); update(1,tmp1,tmp2,tmp3); } } } return 0; }
投递银联等公司10个岗位 >
