线段树模版[interval tree][区间更新]

这是线段树带区间更新的模版，用结构体实现的。 LightOJ - 1112 Curious Robin Hood [interval tree] 这个题线段树的实现方法是用区间去推节点位置，感觉两个的理解难度都差不多。

---

#include<algorithm> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<vector> #include<queue> #include<stack> #include<iomanip> #include<string> #include<climits> #include<cmath> #define MAX 110000 #define LL long long using namespace std; LL n,m; LL ans; struct Tree { LL l,r; LL sum,add; }; Tree tree[MAX*3]; //树的节点数大概小于3n，一般情况下会超过2*n. void pushup(LL x)// 自下向上更新父节点 { LL tmp=2*x; tree[x].sum=tree[tmp].sum+tree[tmp+1].sum; } void pushdown(LL x)//向下推一步 { LL tmp=2*x; tree[tmp].add += tree[x].add; //给做孩子add tree[tmp+1].add += tree[x].add; //给右孩子add tree[tmp].sum += tree[x].add*(tree[tmp].r-tree[tmp].l+1); //更新左孩子的记录的和 tree[tmp+1].sum += tree[x].add*(tree[tmp+1].r-tree[tmp+1].l+1);//更新右孩子记录的和 tree[x].add=0; //把父节点的add 归零说明已经加过了。 这个add 好像是往下更新的时候用到的 }//话说这个方法没有把父节点x更新啊？？？ void build(int l,int r,int x) { //--------------第一步将节点的各成员初始化------------------- tree[x].l=l; tree[x].r=r; tree[x].add=0; //-------------第二步判断是否到达叶结点----------------------- if(l==r)//说明已经到达了叶子节点可以储存数据了 { scanf("%lld",&tree[x].sum); return ; } //-------------第三步二分区间建立孩子节点---------------------- int tmp=x<<1; int mid=(l+r)>>1; build(l,mid,tmp) ;//建立左孩子 build(mid+1,r,tmp+1); //建立右孩子 //--------------第四步记录左右孩子的和在父节点中---------------- pushup(x); //如果在建树的过程中给sum赋值，记得后面要pushup } void update(LL l,LL r,LL c,LL x) { if(r<tree[x].l||l>tree[x].r) return ; //明显不是查询区间的直接跳过 if(l<=tree[x].l&&r>=tree[x].r) { tree[x].add+=c; tree[x].sum+=c*(tree[x].r-tree[x].l+1); return ; }// if(tree[x].add)//如果这个节点未被更新过还有值没加就向下推一步 pushdown(x); LL tmp=x<<1; update(l,r,c,tmp); // !!! update(l,r,c,tmp+1); pushup(x);//对于上面提到的那个问题，这里对父节点进行更新加和 } void query(LL l,LL r,LL x) { if(r<tree[x].l||l>tree[x].r) //要更新的区间不在该区间上 return ; if(l<=tree[x].l&&r>=tree[x].r) //要更新区间包括了该区间 { ans += tree[x].sum; return ; } if(tree[x].add)// 没有拓展的节点 进行拓展 pushdown(x); LL tmp=x<<1; LL mid=(tree[x].l+tree[x].r)>>1; if(r<=mid) query(l,r,tmp); //查询区间在左半边的时候 else if(l>mid) query(l,r,tmp+1); //查询区间在右半边的时候 else // mid卡在查询区间中间的时候 { query(l,mid,tmp); query(mid+1,r,tmp+1); } // pushup(x); } int main() { // freopen("cin.txt","r",stdin); // freopen("cout.txt","w",stdout); while(~scanf("%lld %lld",&n,&m)) { build(1,n,1); char str[5]; while(m--) { scanf("%s",str); if(str[0]=='Q') { LL l,r; scanf("%lld %lld",&l,&r); ans=0; query(l,r,1); printf("%lld\n",ans); } else { LL l,r,c; scanf("%lld %lld %lld",&l,&r,&c); update(l,r,c,1); } } } return 0; }