建树并将树上节点定为初始值，这个过程比较简单，主要是深搜，代码如下struct tree{ int left,right,value;}s[maxn];void build(int i,int left,int right){ s[i].left=left; s[i].right=right; if(left==right) { s[i].value=a[left];//a是这个节点的权值 return ; } build(i*2,left,(left+right)/2); build(i*2+1,(left+right)/2+1,right); s[i].value=s[i*2].value+s[i*2+1].value;}
第二，就是求和了，这里用的方法是每个点加一个add值，代表这个节点的所有叶节点的值都要加上add，而每次往下深搜时，将此节点的add值更新到两个叶子节点上，并将原来这个节点的权值更新。这点学到后面非常重要。void que(int i,int lef,int rig){ if(s[i].add!=0) { s[i].value+=s[i].add*(s[i].right-s[i].left+1); s[2*i].add+=s[i].add; s[2*i+1].add+=s[i].add; s[i].add=0； } if(s[i].left>=lef && s[i].right<=rig) { sum+=s[i].value; return ; } int kk=i*2; if(s[kk].right>=lef)que(kk,lef,rig); if(s[kk+1].left<=rig)que(kk+1,lef,rig);//不断往下深搜}
第三，区间更新，如果当前搜索到的节点被包含在你要修改的区间中，就将此节点的add值更新。void addtree(int i,int val,int lef,int rig){ if(s[i].left>=lef && s[i].right<=rig) { s[i].add+=val; return ; } if(lef>=s[i].left && rig<=s[i].right)s[i].value+=val*(rig-lef+1); else s[i].value+=val*(min(abs(s[i].right-lef+1),abs(rig-s[i].left+1))); if(s[i].add!=0) { s[i].value+=(s[i].right-s[i].left+1)*s[i].add; s[2*i].add+=s[i].add; s[2*i+1].add+=s[i].add;s[i].add=0; } int kk=2*i; if(s[kk].right>=lef)addtree(kk,val,lef,rig); if(s[kk+1].left<=rig)addtree(kk+1,val,lef,rig);}
最后附上源代码#include
Q 表示询问一段区间内所有数的和，C表示把一段区间内所有数加上一个值（ 详见方法的第一步）样例输入10 41 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 样例输出4 55 9
首先先建树，并将每个子节点的值更新，然后往上更新
首先是查找4-4的和，从根节点往下查找
接下来查找1-10的和，同样从根节点往下找
接下来查找2-4的和，最后的答案为三个红框框出的节点的值之和
接着在3-6的节点各加3，先从根节点往下搜，搜到所有红框框住的节点，此时add值就有用了，【4,5】节点中写的3即为此节点的add值，如果后面还有查找的话，就将父节点的add值加到两个子节点上，加给子节点不是平均分配，而是 子节点的add值都加上父节点的add值，并把父节点的add值归零。
区间更新和查询的顺序有所不同，区间更新是先更新add值，再将此节点的add值传递往下传递，查询的顺序则完全相反，这点千万要注意，否则就会错
更新add值操作必须就将父节点的add值加到两个子节点上，加给子节点不是平均分配，而是 子节点的add值都加上父节点的add值，并把父节点的add值归零