上一篇讲到定点更改，可是，线段树最大的作用是对于区间的操作，即对于区间进行整体操作，区间内的每一个值都进行改动，如果直接改的话，会造成数据的大量重复读写，时间消耗高。所以通过进行标记的方式，减少更改次数，降低运行时间。
A Simple Problem with Integers You have N integers, A1, A2, … , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval. Input The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000. The second line contains N numbers, the initial values of A1, A2, … , AN. -1000000000 ≤ Ai ≤ 1000000000. Each of the next Q lines represents an operation. “C a b c” means adding c to each of Aa, Aa+1, … , Ab. -10000 ≤ c ≤ 10000. “Q a b” means querying the sum of Aa, Aa+1, … , Ab. Output You need to answer all Q commands in order. One answer in a line. Sample Input 10 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4 Sample Output 4 55 9 15 Hint The sums may exceed the range of 32-bit integers.
最简单的模板题，为大家讲解标记法的运用。
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; #define maxsize 100010 #define ll long long //每个节点由以下部分构成 //左右边界值，区间和，懒标记（标记处理信息） struct node{ ll lazy,sum; int L,R; }tree[maxsize*4]; //同样是更新区间和 void pushup(int pos) { tree[pos].sum=tree[pos*2].sum+tree[2*pos+1].sum; } //懒标记处理 //划重点！！！ //值得说明的是，这份程序的思路是，标记lazy的时候同时修改区间和，而且修改lazy一定修改区间和，以此保证修改的统一和对应 void pushdown(int pos) { //如果当前懒结点不为0，即对当前区间进行过整体操作 if(tree[pos].lazy!=0) { //当前区间进行处理，则对左右区间也进行相同处理 tree[2*pos].lazy+=tree[pos].lazy; tree[2*pos+1].lazy+=tree[pos].lazy; //左右的和分别是区间内点的个数乘每个点修改的值 tree[2*pos].sum+=tree[pos].lazy*(tree[2*pos].R-tree[2*pos].L+1); tree[2*pos+1].sum+=tree[pos].lazy*(tree[2*pos+1].R-tree[2*pos+1].L+1); //当前懒标记用完，避免重复修改 tree[pos].lazy=0; } } void build(int pos,int left,int right) { //无论哪一个结点，都需要边界信息，所以放在最前面赋值 tree[pos].L=left; tree[pos].R=right; tree[pos].lazy=0; //同样的，叶子节点 if(left==right) { cin>>tree[pos].sum; return; } int mid=(left+right)/2; build(pos*2,left,mid); build(2*pos+1,mid+1,right); pushup(pos); } ll quary(int pos,int left,int right) { if(tree[pos].L==left&&tree[pos].R==right) { return tree[pos].sum; } //划重点！！！ //这一句放在这里很有意思，因为叶子不可能有子节点，因而不需要对lazy向下更新， //放在这里，只有非叶子节点的结点才能够执行到这一步，而这些节点都有向下更新的必要 pushdown(pos); int mid=(tree[pos].L+tree[pos].R)/2; ll res=0; if(right<=mid) { res+=quary(2*pos,left,right); } else if(left>mid) { res+=quary(2*pos+1,left,right); } else { res+=quary(2*pos,left,mid); res+=quary(2*pos+1,mid+1,right); } return res; } //left，right分别是目标区间，和第一篇写的方式不同 void update(int pos,int left,int right,int add) { //找一个恰好的区间就更新lazy，同时按照上面所说更新区间和，此时直接返回，避免向下处理，这也是lazy的存在意义所在 if(tree[pos].L==left&&tree[pos].R==right) { tree[pos].lazy+=add; tree[pos].sum+=(right-left+1)*add;//漏了加号改了好久好久好久 return ; } if(tree[pos].L==tree[pos].R) return; pushdown(pos); int mid=(tree[pos].L+tree[pos].R)/2; if(mid>=right) { update(2*pos,left,right,add); } else if(mid<left) { update(2*pos+1,left,right,add); } else { update(2*pos,left,mid,add); update(2*pos+1,mid+1,right,add); } pushup(pos); } int main() { int n,q,l,r; char ch; while(scanf("%d%d",&n,&q)!=EOF) { getchar(); build(1,1,n); getchar(); while(q--) { scanf("%s",&ch); getchar(); if(ch=='Q') { scanf("%d%d",&l,&r); //printf("%lld\n",quary(1,l,r)); cout<<quary(1,l,r)<<endl; } else { int val; scanf("%d%d%d",&l,&r,&val); update(1,l,r,val); } } } return 0; }代码不懂的地方可以参考前一篇（虽然写法有不同，但是思路是相同的）或者私聊，希望对大家有帮助。 ps：网上代码虽多可是解释很少，这也是我要重写一遍的目的
