线段树是很重要的数据结构，它的扩展性比树状数组强得多。
文章
知乎有一篇文章讲的不错
核心代码
1 | ll tree[N<<2],a[N],tag[N<<2]; |
例题
洛谷P3372 [模板]线段树1
AC代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll tree[N<<2],a[N],tag[N<<2];
ll ls(ll x){return x<<1;}
ll rs(ll x){return x<<1|1;}
void push_up(ll p)
{
tree[p]=tree[ls(p)]+tree[rs(p)];
}
void build(ll p,ll pl,ll pr)
{
tag[p]=0;
if(pl==pr)
{
tree[p]=a[pl];
return;
}
ll mid=(pl+pr)>>1;
build(ls(p),pl,mid);
build(rs(p),mid+1,pr);
push_up(p);
}
void addtag(ll p,ll pl,ll pr,ll d)
{
tag[p]+=d;
tree[p]+=d*(pr-pl+1);
}
void push_down(ll p,ll pl,ll pr)
{
if(tag[p])
{
ll mid=(pl+pr)>>1;
addtag(ls(p),pl,mid,tag[p]);
addtag(rs(p),mid+1,pr,tag[p]);
tag[p]=0;
}
}
void update(ll L,ll R,ll p,ll pl,ll pr,ll d)
{
if(L<=pl&&pr<=R)
{
addtag(p,pl,pr,d);
return;
}
push_down(p,pl,pr);
ll mid=(pl+pr)>>1;
if(L<=mid)
update(L,R,ls(p),pl,mid,d);
if(mid<R)
update(L,R,rs(p),mid+1,pr,d);
push_up(p);
}
ll query(ll L,ll R,ll p,ll pl,ll pr)
{
if(pl>=L&&pr<=R)
return tree[p];
push_down(p,pl,pr);
ll res=0;
ll mid=(pl+pr)>>1;
if(L<=mid)
res+=query(L,R,ls(p),pl,mid);
if(R>mid)
res+=query(L,R,rs(p),mid+1,pr);
return res;
}
int main() {
ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
for(int i=1;i<=m;i++)
{
int op,x,y;
cin>>op>>x>>y;
if(op==1)
{
int k;
cin>>k;
update(x,y,1,1,n,k);
}
else if(op==2)
cout<<query(x,y,1,1,n)<<'\n';
}
return 0;
}