线段树基础

基本思想

线段树是一个基于分治思想的二叉树。对于一个整数序列

A

[

1…

n

]

A[1…n]

A[1…n] 对于树上的每个点维护

A

A

A 序列上的一个区间

[

l

,

r

]

[l,r]

[l,r] 所对应的信息（如最大值、最小值、总和），对于绝大多数满足结合律的区间操作都可以处理。

树形结构

对于一个点

i

i

i 其维护的区间为

[

l

,

r

]

[l,r]

[l,r] 其子节点（包含左右节点）的维护范围是父节点二分后的范围。

如：

• 父节点维护 $[1,6]$
• 则子节点分别维护 $[1,3]$

特别地，根节点维护范围是

[

1

,

n

]

[1,n]

[1,n]。

对于根节点，其节点编号是

1

1

1。对于一个父节点（编号为

i

i

i），其左右儿子编号分别为

2

i

2i

2i 和

2

i

+

1

2i+1

2i+1。

当

l

=

r

l=r

l=r 时，

i

i

i 就是叶子节点。

在结构体中存储节点信息：

struct edge{
int l,r,sum,ad;//ad是懒标记要用到的
}tr[N*4];

维护方式

以求区间和为例。点

i

i

i 对应的区间和为其子节点管辖的区间和，即两子节点的区间和相加。

void pushup(int i){
tr[i].sum = tr[2*i].sum+tr[2*i+1].sum;
}

建树

建树时给每个节点赋初值（边界，叶子节点要给

s

u

m

sum

sum 赋值）。由二分思想，设

m

i

d

=

(

l

+

r

)

/

2

mid = (l+r)/2

mid=(l+r)/2 ，则左右子节点维护的范围分别为

[

l

,

m

i

d

]

[l,mid]

[l,mid]

[

m

i

d

+

1

,

r

]

[mid+1,r]

[mid+1,r]。

void build(int i,int l,int r){
tr[i] = {l,r,a[l]};
if(l==r) return;
int m = l+r >>1;
build(lc,l,m);
build(rc,m+1,r);
pushup(i);
}

区间查询

设要查询的范围是

[

x

,

y

]

[x,y]

[x,y]。

当递归到节点

i

i

i 时，如果节点

i

i

i，的维护范围在

[

x

,

y

]

[x,y]

[x,y] 内，即

x

<

=

l

x<=l

x<=l 且

r

<

=

y

r<=y

r<=y，返回点

i

i

i 的区间和； 否则判断

i

i

i 的子节点是否在范围内，如果是，就继续向下遍历，且统计答案。

int query(int i,int x,int y){
if(x<=tr[i].l&&tr[i].r<=y){
return tr[i].sum;
}
int sum = 0,m = tr[i].l+tr[i].r>>1;
pushdown(i);//懒标记
if(x<=m) sum+=query(lc,x,y);
if(m<y) sum+=query(rc,x,y);
return sum;
}

区间修改

和区间查询差不多，如果当前节点在范围内，将求和值加上区间范围即可。

void update(int i,int x,int y,int k){
if(x<=tr[i].l&&tr[i].r<=y){
tr[i].ad += k;//懒标记
tr[i].sum += k*(tr[i].r–tr[i].l+1);
return;
}
pushdown(i);//懒标记
int m = tr[i].l+tr[i].r>>1;
if(x<=m) update(lc,x,y,k);
if(m<y) update(rc,x,y,k);
pushup(i);
}

懒标记

对一个修改操作正常情况下，需要

n

n

n 次操作，那线段树的修改就退化到

O

(

n

)

O(n)

O(n) 了。

懒标记只对“完全覆盖”的节点起作用，不会立即影响子节点，直到后续操作需要访问子节点时才下传。需要的时候就是 区间查询、下一次区间修改查到点

i

i

i。

void pushdown(int i){
if(tr[i].ad){
tr[lc].ad += tr[i].ad;
tr[rc].ad += tr[i].ad;
tr[lc].sum+= tr[i].ad*(tr[lc].r–tr[lc].l+1);
tr[rc].sum+= tr[i].ad*(tr[rc].r–tr[rc].l+1);
tr[i].ad = 0;
}
}

全部代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
int n,m,a[N],op,x,y,k;
#define lc i<<1
#define rc i<<1|1
struct edge{
int l,r,sum,ad;
}tr[N*4];
void pushdown(int i){
if(tr[i].ad){
tr[lc].ad += tr[i].ad;
tr[rc].ad += tr[i].ad;
tr[lc].sum+= tr[i].ad*(tr[lc].r–tr[lc].l+1);
tr[rc].sum+= tr[i].ad*(tr[rc].r–tr[rc].l+1);
tr[i].ad = 0;
}
}
void pushup(int i){
tr[i].sum = tr[lc].sum+tr[rc].sum;
}
void build(int i,int l,int r){
tr[i] = {l,r,a[l]};
if(l==r) return;
int m = l+r >>1;
build(lc,l,m);
build(rc,m+1,r);
pushup(i);
}
void update(int i,int x,int y,int k){
if(x<=tr[i].l&&tr[i].r<=y){
tr[i].ad += k;
tr[i].sum += k*(tr[i].r–tr[i].l+1);
return;
}
pushdown(i);
int m = tr[i].l+tr[i].r>>1;
if(x<=m) update(lc,x,y,k);
if(m<y) update(rc,x,y,k);
pushup(i);
}
int query(int i,int x,int y){
if(x<=tr[i].l&&tr[i].r<=y){
return tr[i].sum;
}
int sum = 0,m = tr[i].l+tr[i].r>>1;
pushdown(i);
if(x<=m) sum+=query(lc,x,y);
if(m<y) sum+=query(rc,x,y);
return sum;
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i = 1;i<=n;i++) scanf("%lld",&a[i]);
build(1,1,n);
for(int i = 1;i<=m;i++){
scanf("%lld%lld%lld",&op,&x,&y);
if(op==1){
scanf("%lld", &k);
update(1,x,y,k);
}
else{
printf("%lld\\n",query(1,x,y));
}
}

return 0;
}

例题（模版）：P3372 【模板】线段树 1

时间复杂度

• 建树 $O(n)$
• 修改 $O(lo{g}_{2}n)$
• 查询 $O(lo{g}_{2}n)$

空间复杂度 $O(4n)$