先来看一道题
在数列长度短，询问少时用暴力的方法是可行的。当n,m过大时，时间复杂度就过高了。
在这题里，线段树的思想就是提前将一些区间上的值先计算出来，就是现在我们不是一个数一个数的去累加，而是分成几个区间去去和，并保存成一棵树。对于一个有n个数的数列，树的第一个节点表示的区间就是[1,n],第2*1个是它的右节点，区间范围[1,(1+n)\2], 第2*1+1个节点是它的左节点，区间范围[(1+n)/2+1,n],以此类推。
int built(int l,int r,int root)
{ if(l==r)
{tree[root].suma=f[l];//叶节点记录单个数值
tree[root].su=1;return 0;
}
else
{int mid=(l+r)>>1;
built(l,mid,root*2);
built(mid+1,r,root*2+1);
tree[root].suma=tree[root*2].suma+tree[root*2+1].suma;//根节点的值等于右儿子加左儿子
tree[root].su=tree[root*2].su+tree[root*2+1].su;//记录该区间下内数的个数
}
}
查询区间的值
对于一个root来说，可分分为三种情况
1 y<root 的左节点（l1）
则下一步应该到root的左节点寻找
2 x>root 的右节点（r1）
下一步到root的右节点寻找
3 mid = (x+y)>>1
此时 l <= mid <= r
则左右两个节点都应该进行查询
long long find(int l1,int r1,int root,int st,int end)//[st,end]询问区间，root当前的节点，l1,r1当前的范围
{ if(l1==st&&end==r1)
return tree[root].suma;//找到区间
int mid=(l1+r1)>>1;
if(st>=mid+1)//三种情况
return find(mid+1,r1,root*2+1,st,end);
else
if(end<=mid)
return find(l1,mid,root*2,st,end);
else
if(st<=mid&&end>=mid)
return find(l1,mid,root*2,st,mid)+find(mid+1,r1,root*2+1,mid+1,end);
}
区间相加跟查询操作类似
int jia(int l,int r,int root,int st,int end,int g)//g为要给区间相加的值
{ if(l==st&&end==r)
{ tree[root].suma+=tree[root].su*g;
return 0;
}
int mid=(l+r)>>1;
if(st>=mid+1)
jia(mid+1,r,root*2+1,st,end,g);
else
if(end<=mid)
jia(l,mid,root*2,st,end,g);
else
if(st<=mid&&end>=mid+1)
{jia(l,mid,root*2,st,mid,g);
jia(mid+1,r,root*2+1,mid+1,end,g);
}
tree[root].suma=tree[root*2].suma+tree[root*2+1].suma;
这时，我们再考虑一个问题，是不是每次给区间加数都要加到每一个数上，有些区间可能被询问次数很少，而加数的次数很多，那这种效率是很低。这时我们可以不直接给数加，而是给一整个区间加，只有当需要区间里的数我们才把此时该区间累计的相加下方到子区间。比如现在[1,5] 要加上一个数5，那我直接把5加到这个区间上，当需要它的子区间[1,3]时，我们就把5加到它的子区间上。所以我们才在刚开始建树时，统计区间的个数，当我们需要一个区间的数时，如果被包含，直接返回它的值，否则，下发懒惰标记，到子区间里去查询。
void update(int root)//更新懒惰标记
{ tree[root*2].mark+=tree[root].mark;//懒惰标记下发给子区间
tree[root*2+1].mark+=tree[root].mark;
tree[root*2].suma+=tree[root].mark*tree[root*2].su;//给子区间加数
tree[root*2+1].suma+=tree[root].mark*tree[root*2+1].su;
tree[root].mark=0;return;
}//mark 为懒惰标记，为0说明没有要相加的数
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 struct ff
5 { long long suma;//值
6 int su;统计个数
7 long long mark//懒惰标记;
8 }tree[1000005];
9 int f[1000005];
10 int built(int l,int r,int root)
11 { if(l==r)
12 {tree[root].suma=f[l];
13 tree[root].su=1;return 0;
14 }
15 else
16 {int mid=(l+r)>>1;
17 built(l,mid,root*2);
18 built(mid+1,r,root*2+1);
19 tree[root].suma=tree[root*2].suma+tree[root*2+1].suma;
20 tree[root].su=tree[root*2].su+tree[root*2+1].su;
21 }
22 }
23 void update(int root)
24 { tree[root*2].mark+=tree[root].mark;
25 tree[root*2+1].mark+=tree[root].mark;
26 tree[root*2].suma+=tree[root].mark*tree[root*2].su;
27 tree[root*2+1].suma+=tree[root].mark*tree[root*2+1].su;
28 tree[root].mark=0;return;
29 }
30 long long find(int l1,int r1,int root,int st,int end)
31 { if(l1==st&&end==r1)
32 return tree[root].suma;
33 if(tree[root].mark!=0)
34 update(root);
35 int mid=(l1+r1)>>1;
36 if(st>=mid+1)
37 return find(mid+1,r1,root*2+1,st,end);
38 else
39 if(end<=mid)
40 return find(l1,mid,root*2,st,end);
41 else
42 if(st<=mid&&end>=mid)
43 return find(l1,mid,root*2,st,mid)+find(mid+1,r1,root*2+1,mid+1,end);
44 }
45 int jia(int l,int r,int root,int st,int end,int g)
46 { if(l==st&&end==r)
47 { tree[root].suma+=tree[root].su*g;
48 tree[root].mark+=g;给懒惰标记加，不继续往下加
49 return 0;
50 }
51 if(tree[root].mark!=0)//下放懒惰标记
52 update(root);
53 int mid=(l+r)>>1;
54 if(st>=mid+1)
55 jia(mid+1,r,root*2+1,st,end,g);
56 else
57 if(end<=mid)
58 jia(l,mid,root*2,st,end,g);
59 else
60 if(st<=mid&&end>=mid+1)
61 {jia(l,mid,root*2,st,mid,g);
62 jia(mid+1,r,root*2+1,mid+1,end,g);
63 }
64 tree[root].suma=tree[root*2].suma+tree[root*2+1].suma;
65 }
66 int main()
67 {int n,m,a,x,y,k;
68 cin>>n>>m;
69 for(int i=1;i<=n;++i)
70 cin>>f[i];
71 built(1,n,1);
72 for(int i=1;i<=m;++i)
73 { cin>>a;
74 if(a==1)
75 { cin>>x>>y>>k;
76 jia(1,n,1,x,y,k);
77 }
78 else
79 {cin>>x>>y;
80 cout<<find(1,n,1,x,y)<<endl;
81 }
82 }
83 return 0;
84 }
完整代码