线段树

Introduction Chapter

有一类问题,数据通常可以建模到数轴或是数列上,操作一般是每次对数轴上的一个区间或是数列中的连续若干个数进行修改、查询等,数据规模往往比较大。这些数据就适合用线段树维护。

树型数据结构的基本思想是对数据进行某种方式的划分,以便对所处理的问题进行分治。树中节点所代表的一般是单个元素,也可以是一个区间。比如线段树。它就是一种根据索引信息(元素下标)对元素进行划分的数据结构。

  • 线段树的每个节点都代表一个区间
  • 线段树具有唯一的根节点,代表的区间是整个统计范围 [1,N)[1,N)
  • 线段树的每个叶节点都代表一个长度为 11 的原区间 [x,x+1)[x,x+1)

左闭右开绝对是一个好习惯,为什么?

基本操作

在数组中放结构体,每个节点保存其所代表区间的左右端点、懒标记、维护的数据。完全二叉树的左儿子编号为父节点编号 ×2\times 2,右儿子编号为父节点 ×2+1\times 2+1,故不必保存每个节点左右儿子的编号。由于线段树并不一定是完全二叉树或者满二叉树,其最深层的节点可能很空,但是这些空节点所占的数量却可能达到总的节点数的一半左右,所以堆结构的存储方式存在着空间上的浪费。数组要开 4 倍(浪一点可以开成 2i+12^{i+1})。通过离散化把代表区间 [l,r) 的节点存储到 tree[(l+r-1)|(1^(r-1))] 就可以把所有节点映射到 [2l,2r) 上,然而我不知道怎么找左右儿子。

1
2
3
4
5
6
7
8
struct Node {
int l,r;ll sum,tag;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
#define tag(x) tree[x].tag
}tree[N<<2];
int range[N];

初始化

给每个节点赋上其代表区间的左右点,如果是叶节点直接赋值。否则递归地去建左右子树,并传入对应区间的左右端点。回溯时收集左右儿子的信息。

1
2
3
4
5
6
7
8
9
void init(int p,int l,int r) {
l(p)=l;r(p)=r;
if(r-l==1) sum(p)=range[l];
else {
init(p<<1,l,(r+l)>>1);
init(p<<1|1,(r+l)>>1,r);
sum(p)=sum(p<<1)+sum(p<<1|1);
}
}

标记

进行区间加法时,如果使用数组朴素模拟,显然复杂度为 O(N)O(N),而线段树如果暴力修改不但要修改每个叶节点,还要修改所有祖先,复杂度为 O(NlogN)O(N\log N),比数组还辣鸡。这时我们需要让每个节点多维护一个信息 tag。tag 表示当前节点所代表区间内的每个元素需要被修改的信息,此时当前结点已经被修改而其所有后代暂未被修改。

要修改的区间能把当前递归到达的区间完全包含时,就不必再往下递归,只需修改该节点的值,再给该节点打上 tag。在进行需要进入该节点的儿子的操作时,则把该标记下传,直至被操作的区间完全包含递归到达的区间。显然,在打了 tag 的时候,任意区间最多被划分成 logN\log N 个区间,这就保证了线段树的时间复杂度。下面为下传区间加法标记的过程。

1
2
3
4
5
6
7
inline void pass(int p) {
sum(p<<1)+=(r(p<<1)-l(p<<1))*tag(p);
tag(p<<1)+=tag(p);
sum(p<<1|1)+=(r(p<<1|1)-l(p<<1|1))*tag(p);
tag(p<<1|1)+=tag(p);
tag(p)=0;
}

区间加法

区间加法。先修改好被完全覆盖的节点再打标记,然后回溯。对于不完全覆盖的区间,如果有标记就下传,然后判断是否有局部覆盖再进行修改。和初始化类似,回溯时才收集信息。

1
2
3
4
5
6
7
8
9
void modify(int p,int l,int r,ll d) {
if(l(p)>=l&&r(p)<=r) {sum(p)+=d*(r(p)-l(p));tag(p)+=d;}
else {
if(tag(p)) pass(p);
if(l<r(p<<1)) modify(p<<1,l,r,d);
if(r>r(p<<1)) modify(p<<1|1,l,r,d);
sum(p)=sum(p<<1)+sum(p<<1|1);
}
}

区间和查询

与区间加法过程类似,不同在于只要收集左右儿子的和即可。

1
2
3
4
5
6
7
int query(int p,int l,int r) {
if(l(p)>=l&&r(p)<=r) return sum(p);
if(tag(p)) pass(p);int ans=0;
if(l<r(p<<1)) ans+=query(p<<1,l,r);
if(r>r(p<<1)) ans+=query(p<<1|1,l,r);
return ans;
}

区间最值查询

若要维护区间最值,在初始化、修改、查询时收集最值信息即可。

1
2
3
4
5
6
7
int query(int p,int l,int r) {
if(l(p)>=l&&r(p)<=r) return sum(p);
if(tag(p)) pass(p);int ans=0x80000000;
if(l<r(p<<1)) ans=std::max(ans,query(p<<1,l,r));
if(r>r(p<<1)) ans=std::max(ans,query(p<<1|1,l,r));
return ans;
}

Download

进阶操作

如果要在线段树上进行多种操作,一个 tag 显然是不够的。如果这些操作会都会相互影响,就必须规定 tag 下传的顺序。该题要进行区间加法和区间乘法,根据幼儿园逻辑学知识可知要么乘后加要么加后乘(操作顺序,非下传顺序):

  • a+=b;a*=c;
  • a*=c;a+=b;

如果先传乘法标记再传加法标记,显然执行区间乘法时,对于区间和,根据乘法分配律,直接乘上 d 即可;对于乘法标记,根据乘法结合律,只需不断累乘即可;对于加法标记,我们可以发现:

(a+b)×c=a×c+b×c(a+b)\times c=a\times c+b\times c

也就是说,把加法标记也乘一下就行。而进行区间加法时,直接无视乘法标记,按照上面的方式处理即可。

1
2
3
4
5
6
7
8
9
10
11
12
void multiply(int p,int l,int r,int d) {
if(l(p)>=l&&r(p)<=r) {
sum(p)=(sum(p)*d)%P;
mul(p)=(mul(p)*d)%P;
add(p)=(add(p)*d)%P;
} else {
if(add(p)||mul(p)^1) pass(p);
if(l<r(p<<1)) multiply(p<<1,l,r,d);
if(r>r(p<<1)) multiply(p<<1|1,l,r,d);
sum(p)=(sum(p<<1)+sum(p<<1|1))%P;
}
}

区间乘的过程中,我们对要打标记的节点的加法标记乘上 dd ,相当于把等式右边的 b×cb\times c 计算出来了。所以在下传标记时,我们直接把儿子的区间和乘上父节点的乘法标记再加上儿子区间长度乘上父节点的加法标记即可。

1
2
3
4
5
6
7
8
void pass(int p) {
sum(p<<1)=(sum(p<<1)*mul(p)+add(p)*(r(p<<1)-l(p<<1)))%P;
sum(p<<1|1)=(sum(p<<1|1)*mul(p)+add(p)*(r(p<<1|1)-l(p<<1|1)))%P;
mul(p<<1)=(mul(p<<1)*mul(p))%P;mul(p<<1|1)=(mul(p<<1|1)*mul(p))%P;
add(p<<1)=(add(p<<1)*mul(p)+add(p))%P;
add(p<<1|1)=(add(p<<1|1)*mul(p)+add(p))%P;
mul(p)=1;add(p)=0; // 乘法标记应初始化为 1
}

Download

如先传乘法标记再传加法标记,很容易发现,我们很难进行调整使其满足条件。

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

笔记 数据结构

评论

您需要成为穿墙的邪仙以加载 Disqus。