线段树 1 · Aier's blogs

区间操作

我们从一个经典的简单问题开始，给定一个长为 $n$ 的序列和 $q$ 次两种操作：将一个区间里的数加上 $k$ 和求一个区间的和。

如果每次都枚举区间内的每个数操作，复杂度为 $O(nq)$ 。使用前缀和可以将求和操作优化为 $O(1)$ ，差分可以将区间修改操作优化至 $O(1)$ 。但是这两种操作无法同时使用，最坏复杂度仍然为 $O(nq)$ 。

分治结构

将序列不断于区间中点二分，我们可以得到一个高 $O(\log_2 n)$ 的二叉树结构，二叉树上的每个节点对于一个序列的区间，我们让每个节点保存该区间的信息。

flowchart TD
    A["[1,4]"] --> B["[1,2]"]
    A --> C["[3,4]"]
    B --> D["1"]
    B --> E["2"]
    C --> F["3"]
    C --> G["4"]

使用 Build 函数构建这个二叉树，每次递归二分区间然后合并左右节点信息。在区间长度为 $1$ 时对应为叶子节点返回该单点信息。PushUp 函数为合并两个子节点的信息。

void Build(int p,int l,int r) {
    sum(p)={};
    if(l==r) return sum(p)={a[l]},void();   // 叶子节点返回
    int mid=l+r>>1;                         // 区间中点
    Build(ls(p),l,mid),Build(rs(p),mid+1,r);// 构建左右子区间
    PushUp(p);                              // 合并信息
}

对于任意区间，每一层中完全包含于 [l,r] 且不能再向上合并的节点，最多只有两个。因此，任意区间都可以由 $O(\log_2 n)$ 个线段树节点覆盖。于是我们可以将查询的区间分解到这些节点，将操作复杂度降到 $O(\log_2 n)$ 。

使用 Query 函数分治查询区间信息，当查询区间和当前节点无交集返回空信息(单位元)，包含时返回当前区间信息，否则递至子节点并合并子节点的返回信息。

Info Query(int p,int l,int r,int L,int R){
    if(L<=l&&R>=r) return sum(p);    // 完全包含返回当前节点
    if(l>R||r<L) return {};          // 无交集返回空
    int mid=l+r>>1;                  // 有交集合并子节点的返回信息
    return Query(ls(p),l,mid,L,R)+Query(rs(p),mid+1,r,L,R);
}

对于单点的修改操作，不难发现一次操作只会影响到一条从根到叶子的路径上的节点，由于树高 $O(\log_2 n)$ ，单点修改的复杂度就也为 $O(\log_2 n)$ 了。

使用 Change 函数实现单点修改，从根节点递归至要修改的叶子节点，然后回溯时修改这条从根到叶子的链的信息。

void Change(int p,int l,int r,int x,Info k){
    if(l==r) return sum(p)=k,void();   // 修改叶子信息
    int mid=l+r>>1;
    if(x<=mid) Change(ls(p),l,mid,x,k);
    else Change(rs(p),mid+1,r,x,k);
    PushUp(p);                         // 回溯修改链信息
}

懒标记

如果只是通过 $O(n)$ 次单点修改来完成区间加操作，复杂度将会达到 $O(qn\log_2 n)$ ，甚至不如前缀和，考虑利用任意区间可以被分解为 $O(\log_2 n)$ 个树上的节点这个性质优化。

如果只是修改这 $O(\log_2 n)$ 个节点和根到节点的路径，复杂度也为 $O(\log_2 n)$ 。不过这些节点的子孙节点就无法正确使用了。

于是我们给这些节点添加一个暂存的标记信息，用来延迟修改这些点的子孙点的信息。通过这种 懒标记 的方法，我们可以将修改操作也优化至 $O(\log_2 n)$ 。

使用 Add 函数实现懒标记延迟区间修改，当修改区间和当前节点无交集直接返回，完全包含时修改节点并打上懒标记，然后回溯修改所有祖宗节点。PushDown 函数为下放标记至子节点，AddTag 函数为修改该节点信息并打标记。

void Add(int p,int l,int r,int L,int R,Tag k){
    if(L<=l&&R>=r) return AddTag(p,k);  // 完全包含打标记
    if(l>R||r<L) return;                // 无交集返回
    PushDown(p);                        // 下放节点标记至子节点
    int mid=l+r>>1;
    Add(ls(p),l,mid,L,R,k);             // 递归至子节点修改
    Add(rs(p),mid+1,r,L,R,k);
    PushUp(p);                          // 回溯修改
}

除了 Add 函数外，其他进入子节点操作也需要下放标记信息。完整线段树模板代码：

代数信息

并非所有信息都可以用线段树维护。为了完成以上操作，除了线段树的模板外，我们还需要设计一个代数系统。

对于 PushUp 函数，我们要求 Info 信息具有 结合律。即 $(a+b)+ c=a+ (b+ c)$ 。结合律是线段树能进行任意区间分治合并的根本原因。

在 Query 函数里我们需要处理空区间，所以我们还需要 Info 具有 单位元。即我们维护的信息为一个 幺半群。

交换律和逆元？

线段树可以维护没有交换律的信息。但是需要维护一个信息的合并顺序，即 ls+rs 和 rs+ls。

如果使用第二种维护，那我们得到的信息为区间的翻转信息。

线段树也不需要逆元或幂等，因为线段树使用不重叠的区间拼凑出完整信息。

对于 AddTag 函数，我们需要维护一个 Tag 标记信息，每个标记是一个未执行的修改。

Tag 和 Info 的作用是一个 Info 到 Info 的函数，需要满足 分配律，即 $t\oplus(u+v)=(t\oplus u)+(t\oplus v)$ 。

Tag 与 Tag 的复合是 函数复合，满足 $(t_1+t_2)\oplus u=t_2\oplus t_1\oplus u$ 。

如果不能设计出 Tag，Info 也可以使用线段树维护，但是只能使用单点修改。

代码封装为 Tag 和 Info 两个结构体：

struct Tag{
    Tag(){}
    bool operator==(const Tag &x)const{return 1;}
    Tag operator+(const Tag &x){}
};
struct Info{
    Info(){}
    Info operator+(const Info &x)const{}
    Info operator+(const Tag &x)const{}
};

因为区间加区间和太模板了，所以找了别的例题：

我们要维护一个序列，支持区间加修改和区间平均数和方差询问。题目给出了方差的定义：

s^2=\frac{1}{n}\sum\limits_{i=1}^n\left(A_i-\overline A\right)^2 \qquad \overline A = \frac{1}{n}\sum\limits_{i=1}^n A_i

考虑设计 Info 和 Tag 用线段树维护序列。平均数很好维护，只需要区间求和然后除以区间长度。

我们化简方差公式：

s^2=\frac{1}{n}\sum\limits_{i=1}^n\left(A_i-\overline A\right)^2=\frac{1}{n}\sum\limits_{i=1}^n(A_i^2+\overline A^2-2A_i\overline A)

=\frac{1}{n}(\sum\limits_{i=1}^nA_i^2-2\overline A\sum_{i=1}^nA_i)+ \overline A^2

于是我们只需要在额外维护一个平方和，平方和具有结合律和单位元，可以直接由线段树维护。

考虑设计一个 Tag 维护区间加法操作，我们有公式：

(A+k)^2=A^2+k^2+2Ak \qquad (A+(k_1+k_2))^2=(A+k_1+k_2)^2

所以我们可以设计 Info 和 Tag 为

struct Tag{
    double add;
    bool operator==(const Tag &x)const{return add==x.add;}
    Tag operator+(const Tag &x)const{return {add+x.add};}
};
struct Info{
    double sum,sum2,len;
    Info operator+(const Info &x)const{
        return {sum+x.sum,sum2+x.sum2,len+x.len};
    }
    Info operator+(const Tag &x)const{
        return {sum+x.add*len,sum2+2*x.add*sum+x.add*x.add*len,len};
    }
};

AC 代码：

本题为单点修改，区间最大子段和。考虑如果没有修改，只是查询全局最大子段和，我们有一个简单的分治做法。

对于一个区间，我们按中点分治，把最大子段和分为三种情况

完全在中点右侧
完全在中点左侧
跨过区间中点

于是我们只计算第三种情况，前两种递归至下一层计算。有跨过区间中点的可以由左区间的后缀最大值和右区间的前缀最大值相加得到，我们就完成了全局最大子段和的计算。

考虑将这个过程放在同样是分治结构的线段树上维护，我们设计一个 Info 信息。我们需要维护之前提到的最大子段和 $Ans$ ，前缀最大值 $Pre$ 和后缀最大值 $Suf$ 。其中

Ans=\max(Ans_{ls},Ans_{rs},Pre_{rs}+Suf_{ls})

如果前缀最大值不跨过中点，可以由 ls 的前缀最大值得到。如果跨过中点，就可以由 ls 的总和 $Sum$ 加 rs 的前缀最大值得到。后缀最大值也同理，所以我们还需要再维护一个区间和信息。

Pre=\max(Pre_{ls},Sum_{ls}+Pre_{rs}) \qquad Suf=\max(Suf_{rs},Sum_{rs}+Suf_{ls})

注意我们的单位元不可以使用默认构造，因为 $\max$ 操作的单位元是 $-\infin$ ，我们要把所有用到 $\max$ 操作的值默认为 $-\infin$ 。设计出 Info 如下：

struct Info{
    ll ans,pre,suf,sum;
    Info(){ans=pre=suf=-INF,sum=0;}
    Info(ll a,ll p,ll s,ll t){ans=a,pre=p,suf=s,sum=t;}
    Info operator+(const Info &x)const{
        return {max({ans,x.ans,suf+x.pre}),max(pre,sum+x.pre),max(x.suf,x.sum+suf),sum+x.sum};
    }
};

因为本题不用区间修改，所以我们不用设计 Tag。不过读者可以自行思考如果区间修改需要怎么做。给出本题 AC 代码：

附录

我们使用 ls(p)=(p<<1) rs(p)=(p<<1|1) 作为 p 的左右儿子，根节点为 $1$ 。这样不需要使用指针跳转，常数比较小。但是这样标号可能会留下空洞，虽然只有 $2n-1$ 个节点但是我们要开 $4n$ 的空间。

线段树的扩展内容会在后续博客中讲解