线段树理论笔记

0.前言

侧重于理论以及做题大方向，方法论的指导。

本博客若没有特殊说明，所有变量默认取值范围为 $\mathbb{Z}$ 。

1.半群线段树

1.1 定义

我们都说，线段树能维护具有结合律的信息，不能维护没有结合律的信息，那么为什么线段树只能维护有结合律的信息呢？这里我们可以利用半群线段树的理论来进行说明。

首先要定义什么是半群，半群是一个二元组 $(S,\times)$ ，其中：

$S$ 是一个非空集合；
$\times$ 是一个定义在 $S$ 上的运算，即 $x\in S,y\in S,x\times y=z,z\in S$ ，即满足封闭性。
这个 $\times$ 运算满足结合律，即 $(x\times y)\times z=x\times(y\times z)$ 。

注意这里上面的 $\times$ 不是乘法，是抽象代数中的集合运算，这里用乘法符号让读者更好理解。同时要注意，半群并不要求拥有单位元和逆元。

而半群线段树是一种数据结构，可以维护一个序列 $a_1,a_2,\dots,a_n$ ，其中 $a_i \in S$ ， $(S,\times)$ 是一个半群，支持操作：

单点修改，即给定 $x,k(1\le x \le n,k\in S)$ ，令 $a_x \leftarrow k$ 。
区间查询，即给定 $l,r(1\le l \le r \le n)$ ，求 $a_l \times a_{l+1} \times \dots \times a_r$ 。

而对于实现的时候我们当然就是用线段树的结构啦，代表区间 $[l,r]$ 的节点 $i$ 上记录了 $a_l \times a_{l+1} \times \dots \times a_r$ 的信息。修改的时候单点修改，从叶子自底向上，按照 $t_i=t_{lson}\times t_{rson}$ 的顺序从底往上合并（就是我们写的 pushup 函数），假设我们一次运算 $\times$ 的时间复杂度是 $k$ ，那么一次查询和修改的时间复杂度就是 $O(k\log n)$ 。

而对于半群线段树的实现，我们可以把节点写成一个结构体的形式，让后重载运算符，这样的话你每一次写半群线段树的形式代码时候，就可以真正的按照 “模板” 来去写了。

当然要注意的一点，我们这里定义的乘法运算是没有交换律的，所以你不能瞎 pushup，根据上面定义可以知道 $t_i \neq t_{rson}\times t_{lson}$ ，大家做题应该体会过 pushup 写错の痛。

这里我们并没有说懒标记，其实懒标记从一开始我们学习线段树的时候，它的出现其实就是将许多的单点修改转化为了一次对于区间上的单点修改，所以对于懒标记来说，我们同样需要满足结合律和封闭性，但是我们没有必要满足交换律，我们通过及时地 pushdown 记都是将当前懒标记对应的操作序列接在原懒标记对应的操作序列之后，即我们按时间顺序处理所有懒标记。

对于懒标记线段树,他不一定满足我们上面所提到半群的性质，我们第二章会提到。

相对的，区间修改要维护的信息可能会比单点修改要更多。

1.2 应用

应用比如说有区间和，区间最大最小值，维护矩阵乘法，维护哈希值等。

区间求和与区间求积

我不知道 $2+3$ 等于几，但是我知道 $2+3=3+2$ ，因为实数集上的加法运算构成阿贝尔群。

实数和加法当然构成群啦，因为加法即满足结合律，也满足交换律，所以我们可以通过线段树来维护加法操作，乘法当然也是同理的。

线段树维护矩阵乘法

不知道大家有没有做过动态 DP，那个题就是通过线段树加树剖维护矩阵来进行 $O(\log n)$ 的 DP 的。矩阵和矩阵乘法当然满足结合律，而且大家都知道，矩阵乘法满足结合律不满足交换律

线段树维护字符串哈希

这个想必大家在学习字符串哈希的时候应该是见过的，其实字符串哈希的计算过程如下：

H(s) = \left( \sum_{i=0}^{n-1} s_i \cdot base^{n-i-1} \right) \mod m

那么我们定义哈希值上的二元运算 $\oplus$ ，我们令 $S$ 集合中每一个元素为一个二元组 $(h,len)$ ，其中表示如下：

$h$ ：字符串哈希值。
$len$ ：字符串长度

那么运算定义如下：

(h_1, l_1) \otimes (h_2, l_2) = \left( (h_1 \cdot base^{l_2} + h_2) \mod m,\; l_1 + l_2 \right)

可以理解为拼接哈希的过程，下面是我们证明线段树可以通过半群线段树维护哈希值，即证明上述是否能为一个半群，如果你能理解拼接哈希具有结合律和封闭性那么就不用看 www。

封闭性是显然成立的，因为对任意 $ (h_1, l_1), (h_2, l_2) \in \mathcal{S} $：

$ h_1 \cdot b^{l_2} + h_2 \mod m \in \mathbb{Z}_m $
$ l_1 + l_2 \in \mathbb{N} $

所以 $ (h_1, l_1) \otimes (h_2, l_2) \in \mathcal{S} $，封闭性成立。

考虑结合律，我们要证明：

((h_1, l_1) \otimes (h_2, l_2)) \otimes (h_3, l_3) = (h_1, l_1) \otimes ((h_2, l_2) \otimes (h_3, l_3))

算左边：

先算 $ (h_1, l_1) \otimes (h_2, l_2) $：

= (h_1 \cdot b^{l_2} + h_2, \; l_1 + l_2)

再与 $ (h_3, l_3) $ 合并：

= \left( (h_1 \cdot base^{l_2} + h_2) \cdot base^{l_3} + h_3, \; (l_1 + l_2) + l_3 \right) = \left( h_1 \cdot base^{l_2 + l_3} + h_2 \cdot base^{l_3} + h_3, \; l_1 + l_2 + l_3 \right)

算右边：

先算 $ (h_2, l_2) \otimes (h_3, l_3) $：

= (h_2 \cdot base^{l_3} + h_3, \; l_2 + l_3)

再与 $ (h_1, l_1) $ 合并：

= \left( h_1 \cdot base^{l_2 + l_3} + (h_2 \cdot base^{l_3} + h_3), \; l_1 + (l_2 + l_3) \right) = \left( h_1 \cdot base^{l_2 + l_3} + h_2 \cdot base^{l_3} + h_3, \; l_1 + l_2 + l_3 \right)

左右两边相等，结合律成立。

然而都知道拼接哈希的时间复杂度是 $O(1)$ ，所以可以 $O(\log n)$ 支持查询和单点修改。

1.3 一般性的可合并信息

上面都是一般性的问题，但是如果你做过一些仅通过线段树维护的题目的话，你会发现并不想上面一样简单，因为有一些信息它甚至一般情况下都不是传统的乘除加减运算，但是他们的共性就是满足结合律，这个时候我们需要一个更一般性的结论。

我们定义这种可合并的信息，还是从半群的角度入手，设这些信息构成集合 $S$ ，那么有映射（不知道映射的可以理解为函数） $f:([1,n]\cap \mathbb{Z})^2 \to S$ ，说人话就是 $f(x,y) \to S (x,y \in [1,n],\mathbb{Z}$ 。同时定义运算 $\times$ 满足 $S \times S \to S$ 。若满足 $f(l,m)=x,f(m+1,r)=y$ ，那么 $f(l,r)=x\times y$ 。直观理解就是每一个区间对应的都是唯一的值，并且这个运算对于于相邻区间的合并，即 pushup，且封闭性满足能够让我们能够从 $f(l,m),f(m+1,r)$ 能够推出 $f(l,r)$ 。

那么我们根据上面的定义的话，一个区间的信息无论怎么选取 $m$ 拆分为自取件，按照什么顺序合并起来，只要你左右顺序一致的，那么就还能满足 $a_l \times a_{l+1} \times \dots \times a_r$ 这样的结果，这说明这种一般性的可合并取件信息也是构成半群的，可以用我们的半群线段树来去做。

1.4 做题的大方向

那么我们上面说了这么多的例子，感觉好像就是在重新讲一遍单点修改区间查询的线段树，其实不然，我们可以通过给信息设计半群的结构来进行操作。

一般的来说，我们在做类似于线段树的题中我们要考虑的是以下的几步：

观察题目性质。
我需要维护什么？
这种信息是不是什么常见类型，若不是，我能不能通过构造信息和操作，让它构成一个半群？
如果可以的话，我们可不可以通过线段树来进行维护，并且定义的运算符操作是否高效。

最难的地方在于观察题目性质，设计信息和思考信息的合并，下面给出几道例题。

1.5 例题

维护最大子段和

例如区间最大子段和，根据上面我们提出过的一般性的可合并信息的维护。

首先我们分析性质，我们维护的信息要具有结合律和封闭性，通过 $f(l,mid),f(mid+1,r)$ 的信息推出 $f(l,r)$ 。

一个显然的想法就是维护 $ans$ 为区间最大子段和，让后从左右区间传递上来，但是这样的操作是不满足封闭性的，因为我们丢弃了跨区间 $mid$ 的合并信息。而注意到跨过 $mid$ 的区间是通过 $[l,mid]$ 的最大后缀以及 $[mid+1,r]$ 的最大前缀拼在一起，那么我们可以考虑维护区间最大前后缀和 $pre,suf$ ，这样的话我们 $ans$ 就可以这么合并：

ans\leftarrow \max\{ ans_{ls},ans_{rs},suf_{ls}+pre_{rs} \}

现在 $ans$ 满足我们性质的，并且好处是这个运算显然是满足结合律与封闭性的，但是我们现在要考虑维护 $pre,suf$ 了 www。

考虑 $pre,suf$ ，前缀后缀和当然也是要考虑跨区间的贡献，注意到跨区间的贡献，例如 $pre$ ，一定是 $pre_{ls}$ 或者 $sum_{ls}+pre_{rs}$ 所构成的，其中 $sum$ 是区间和，同理于 $suf$ ，这样的信息合并设计也是满足结合律的。

总结一下我们需要维护什么信息：

$ans$ ：区间最大子段和，合并为 $ans\leftarrow \max\{ ans_{ls},ans_{rs},suf_{ls}+pre_{rs} \}$ 。
$pre$ ：区间最大前缀和，合并为 $pre\leftarrow \max \{ pre_{ls},sum_{ls}+pre_{rs} \}$ 。
$suf$ ：区间最大后缀和，合并基本同上，这里不再给出。
$sum$ ：区间和，合并不给出。

读者可以感受我们上面所提出的设计信息构造半群的流程，我们首先要从我们所求出的答案开始，让后考虑答案如何从子区间的信息合并上来，再一开始的时候可能是不满足半群所要求的封闭性，为此我们要敢于构造信息以满足封闭性，让后我们再考虑构造出来的信息如何从子区间合并上来。

重复上面的过程，直到我们的半群合并并且信息封闭，这种方法比我们一开始要想出所有要维护的信息是更简单的。

CF1076G

区间修改和区间查询，但是我们要维护的是一个博弈论的状态，首先我们肯定不是从线段树来去思考，而是先去思考我们维护信息的特殊性质。

我们先考虑 $[1,n]$ 的时候该怎么做，显然有一个 DP，设 $f_i$ 表示跳到第 $i$ 个格子的时候是先手必胜还是先手必败，考虑倒过来 DP，注意到我们的信息只关注就行即可，那么有转移：

当 $a_i$ 为奇数的时候， $f_i=1$ 。这时显然无论怎么跳后手一定是跳出去的。
当 $a_i$ 为偶数的时候， $f_i$ 能否先手必赢当且仅当后面 $m$ 个格子中没有先手必败状态。

时间复杂度为 $O(nmq)$ 无法通过。

考虑优化，本题目的瓶颈在于我们要知道后面 $m$ 个格子中有没有先手必败，同时观察到我们要维护的信息是一个 0/1 序列，而且 $m$ 极小，考虑状压 DP 值，对于线段树上每一个区间，记录 $[r+1,r+m]$ 的 DP 状态状压为 $S$ ，让后考虑我们 $[l,l+m-1]$ 的 DP 信息是什么，合并考虑到结合律是显然的（因为是这么定义的 www），封闭性同理，可以用线段树维护。

让后考虑区间修改，我们维护的信息只具有奇偶性，区间加偶数显然没有任何卵用，但是区间加奇数会使得区间奇偶性翻转，我们考虑维护一个区间翻转 tag，同时答案维护两份，一份是正常的答案，一份是反转过后的，区间翻转奇偶性的时候交换两份答案即可。但是注意到一次合并信息的时间复杂度过高，考虑优化运算操作，注意到我们每次都要便利这个 $S$ 的状态，其实我们只需要知道 $S$ 中第一个 0 的位置就可以了，这样就足够高效了，时间复杂度为 $O(qm\log n)$ 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=5e5+15;
int n,m,q,a[MN];

struct Segment{
#define ls p<<1
#define rs p<<1|1

    struct QWQ{
        int pos[11];
        
        QWQ operator +(const QWQ &x)const{
            QWQ ret;
            for(int i=1;i<=m+1;i++){
                ret.pos[i]=pos[x.pos[i]];
            }
            return ret;
        }
    };

    struct Node{
        int l,r;
        int isrev;
        QWQ val[2];
    }t[MN<<2];

    void dorev(int p){
        swap(t[p].val[1],t[p].val[0]);
        t[p].isrev^=1;
    }

    void pushdown(int p){
        if(t[p].isrev){
            dorev(ls);
            dorev(rs);
            t[p].isrev=0;
        }
    }

    void pushup(int p){
        t[p].val[0]=t[ls].val[0]+t[rs].val[0];
        t[p].val[1]=t[ls].val[1]+t[rs].val[1];
    }

    void build(int p,int l,int r){
        t[p].l=l;
        t[p].r=r;
        if(l==r){
            for(int i=1;i<=m;i++){
                t[p].val[0].pos[i]=t[p].val[1].pos[i]=i+1;
            }
            if(a[l]==1){
                t[p].val[1].pos[m+1]=m+1;
                t[p].val[0].pos[m+1]=1;
            }else{
                t[p].val[1].pos[m+1]=1;
                t[p].val[0].pos[m+1]=m+1;
            }
            return;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        pushup(p);
    }

    void modify(int p,int fl,int fr){
        if(t[p].l>=fl&&t[p].r<=fr){
            dorev(p);
            return;
        }
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(mid>=fl) modify(ls,fl,fr);
        if(mid<fr) modify(rs,fl,fr);
        pushup(p);
    }

    QWQ query(int p,int fl,int fr){
        if(t[p].l>=fl&&t[p].r<=fr){
            return t[p].val[1];
        }
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(mid<fl) return query(rs,fl,fr);
        if(mid>=fr) return query(ls,fl,fr);
        return query(ls,fl,fr)+query(rs,fl,fr);
    }
}sg;

signed main(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]=(a[i]&1)^1;
    }
    sg.build(1,1,n);
    while(q--){
        int op,l,r,x;
        cin>>op>>l>>r;
        if(op==1){
            cin>>x;
            if(x&1) sg.modify(1,l,r);
        }else{
            auto ret=sg.query(1,l,r);
            if(ret.pos[m+1]==1){
                cout<<"2\n";
            }else cout<<"1\n";
        }
    }
    return 0;
}

CF1149C

还是我们的套路，我们不可能一次就想着把所有信息的设计完毕，我们先从听我们要维护的信息的特殊性质入手，让后我们再进行信息的设计使其能够满足半群的性质。

此处的 ( 和 ) 本质上可以看做欧拉序中通过一条边搜索以及回溯的过程，对应深度分别自增或者自减。

那么我们把 ( 看做深度加 1，而 ) 看作为深度减 1，计算前缀和数组 $p_i$ ，那么 $p_i$ 对应的就是欧拉序中第 $i+1$ 点的深度（第一个点是根）。

那么对于欧拉序上第 $l$ 个点 $u$ 和第 $r$ 个点 $v$ ，设 $w=\operatorname{lca}(u,v)$ ，那么有：

\begin{aligned} dep_u &= p_{l-1},dep_v =p_{r-1},dep_w =\min_{i=l-1}^{r-1}p_i \\ dis(u,v)&=dep_u +dep_v -2dep_w=p_{l-1}+p_{r-1}-2\min_{i=l-1}^{r-1} p_i \end{aligned}

注意到一次修改会修改一个后缀并且让区间加减 2，考虑维护如下操作：

对所有的 $1\le l \le r \le 2n-1$ 求 $p_{l-1}+p_{r-1}-2\min_{i=l-1}^{r-1} p_i$ 的最大值。

考虑用线段树维护答案，首先我们肯定需要维护一个区间最小深度，即 $mn$ ，区间最大深度 $mx$ ，和当前区间的答案 $ans$ 。

当然 $ans$ 是不封闭的，因为如果我们合并两个区间的答案的话就忽略了 $lca$ 在哪个的问题。

我们考虑我们维护的信息 $p_{l-1}+p_{r-1}-2\min_{i=l-1}^{r-1} p_i$ 可以拆分为 $(x-2\min_{i=l-1}^{r-1} p_i)+y$ ，考虑维护前半部分，这样好处就是我们可以方便的处理 LCA 的问题。

考虑对于每一个区间维护 $p_{l-1}-w\min_{i=l-1}^{r-1} p_i,p_{r-1}-w\min_{i=l-1}^{r-1} p_i$ ，记作 $lmx,rmx$ 。那么 $ans$ 转移是有：

ans\leftarrow \max \{ ans_{ls},ans_{rs},rmx_{ls}+mx_{rs},mx_{ls}+lmx_{rs} \}

区间操作打标记即可，时间复杂度 $O(m\log n)$ 。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1e6+15;
int n,q,a[MN],sum[MN];

struct Segment{
    #define ls p<<1
    #define rs p<<1|1

    struct Node{
        int l,r,mx,mn,lmx,rmx,ans,add;
    }t[MN<<2];

    void pushup(int p){
        t[p].mx=max(t[ls].mx,t[rs].mx);
        t[p].mn=min(t[ls].mn,t[rs].mn);
        t[p].lmx=max({t[ls].lmx,t[rs].lmx,t[rs].mx-2*t[ls].mn});
        t[p].rmx=max({t[ls].rmx,t[rs].rmx,t[ls].mx-2*t[rs].mn});
        t[p].ans=max({t[ls].ans,t[rs].ans,t[ls].mx+t[rs].lmx,t[rs].mx+t[ls].rmx});
    }

    void doadd(int p,int k){
        t[p].add+=k;
        t[p].mx+=k,t[p].mn+=k;
        t[p].lmx-=k;
        t[p].rmx-=k;
    }

    void pushdown(int p){
        if(t[p].add){
            doadd(ls,t[p].add);
            doadd(rs,t[p].add);
            t[p].add=0;
        }
    }

    void build(int p,int l,int r){
        t[p].l=l;
        t[p].r=r;
        if(l==r){
            t[p].mx=t[p].mn=sum[l];
            t[p].lmx=t[p].rmx=-sum[l];
            t[p].ans=0;
            return;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        pushup(p);
    }

    void modify(int p,int pos,int k){
        if(t[p].l==t[p].r){
            doadd(p,k);
            return;
        }
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(mid>=pos){
            modify(ls,pos,k);
            doadd(rs,k);
        }else modify(rs,pos,k);
        pushup(p);
    }
}sg;


int main(){
    cin>>n>>q;
    n=(n<<1)-1;
    for(int i=2;i<=n;i++){
        char qwq;
        cin>>qwq;
        a[i]=(qwq=='('?1:-1);
    }
    a[1]=1;
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+a[i];
    }
    sg.build(1,1,n);
    cout<<sg.t[1].ans<<'\n';
    while(q--){
        int x,y;
        cin>>x>>y;
        ++x,++y;
        if(a[x]==1){
            sg.modify(1,x,-2);
            a[x]=-1;
        }else{
            sg.modify(1,x,2);
            a[x]=1;
        }
        if(a[y]==1){
            sg.modify(1,y,-2);
            a[y]=-1;
        }else{
            sg.modify(1,y,2);
            a[y]=1;
        }
        cout<<sg.t[1].ans<<'\n';
    }


    return 0;
}

2. 环线段树

这里的环可不是图论的环，环指的是一个元素集合和乘法、加法运算，乘法满足结合律，加法满足结合律、交换律，乘法与加法满足分配率，我们写作 $(S,\times,+)$ 。

特别注意上面的加法操作是具有交换律的。

而环线段树对应一种数据结构，可以维护一个序列 $a_1,a_2,\dots,a_n$ ，其中 $a_i \in S$ ， $(S,\times,+)$ 是一个环，支持操作：

区间修改：给定 $l,r,x$ ，对于所有 $l\le i \le r$ ，令 $a_i \leftarrow x\times a_i$ 。
区间查询，即给定 $l,r(1\le l \le r \le n)$ ，求 $a_l + a_{l+1} + \dots + a_r$ 。

这种线段树就是我们所说的 LazyTag 线段树。相比于半群线段树在环线段树上的节点 $i$ 除了要维护所谓的 $s_i \in S$ 上之外，还要维护 $t_i \in S$ 代表 “懒标记”，其意味着节点 $i$ 的子树尚有一些修改没有下穿，这些修改等效于左乘 $T_i$ 。

修改，查询的时候可能需要将标记下传。当要查询左右儿子的时候，我们将懒标记下传至左右儿子更新 $s,t$ ，让后将当前节点的 $t_i$ 重置为所谓的 “单位元”。

通常而言，若一次运算的时间复杂度为 $O(k)$ ，那么修改查询时间复杂度为 $O(k\log n)。

2.1 将 val 和 tag 分离

有的时候，环线段树并不能很好地描述我们所要做的事情，而是我们要把所谓的 val 和 tag 认为是不同的东西。

具体来说，就是我们要把线段树所存储的值集合 $D$ 和标记集合分开，设标记集合为 $E$ ，那么有运算：

$\times$ ： $E\oplus D \to D$ ，表示给某个值下传标记的结果。
$\times$ ： $E\oplus E \to E$ ，表示标记的下传，有结合律。
$+$ ： $D \oplus D \to D$ ，表示值得求和，与 $E,D$ 见乘法有分配律。

如果要直观理解的话，那么就是 $D$ 为 $n$ 维向量的集合， $E$ 为 $n\times n$ 矩阵的集合。

那么对应到修改为区间左乘 $x(x\in E)$ ，而查询为求区间值和。

2.2 应用

间加区间和、区间加乘区间和、区间加区间历史最大值、区间加区间历史版本和都
可以 “环线段树” 做。

接下来我们会大量设计矩阵操作，用于演示 val 和 tag 分离的操作，可以看下面的图来显理解：

区间加乘区间和

观察区间加乘的本质其实是什么：

加： $a_i \leftarrow a_i +x=a_i +1\times x$ （这里的 $\times$ 就是乘号）。
乘： $a_i \leftarrow ka_i$ 。

这两个都是线性变换耶，我们可以考虑维护一个向量： $[a_i,1]$ ，，那么每次修改相当于就是乘上一个 $2\times 2$ 的矩阵。而矩阵与其乘法加法都是构成环的（满足分配律），所以可以用环线段树来去做。

区间加区间历史版本和

考虑维护向量序列 $[a_i,h_i,1]$ ，表示原序列值，历史版本和，和方便用的常数。那么操作就是：

加： $a_i \lfetarrow a_i +x\times 1$ ，显然线性变换。
累加历史版本： $h_i\leftarrow h_i+a_i$ ，显然线性变换。

所以也是可以用环线段树做的。

然而实际上你会发现几乎很少人会真的去那么写，因为矩阵实在是太慢了，有一个 $3^3$ 的常数摆在那里。

但是这种想法，矩阵当然是很好想的啦，总比想不出来好吧，毕竟可以骗骗分，让后根据矩阵的特性进行优化 blablalba。

2.3 例题

做题时的重心仍然要放在观察性质与构造信息上，但是因为我们有了懒标记，所以要考虑的比半群线段树要更多一些。

[NOIP2022] 比赛

询问过于逆天，正难则反，考虑每个 $a_i,b_i$ 会在哪些区间作为最大值，这个区间信息我们可以通过单调栈 $O(n)$ 求出。

我们把区间看成平面上的一个点。每个点上维护向量 $[mx_a,mx_b,v,1]$ ，其中 $mx_a \cdot mx_b$ ，那么有修改：

矩形范围内 $mx_a$ 加 $x$ ： $mx_a \leftarrow mx_a +x \cdot 1,v\leftarrow v+x \cdot mx_b$ 。
矩形范围内 $mx_b$ 加 $x$ ： $mx_b \leftarrow mx_b +x \cdot 1,v\leftarrow v+x \cdot mx_a$ 。

都是线性变化，而查询查询的就是矩形范围内 $v$ 的和，矩形范围求和我们可以用过对一维差分，转化为两个区间历史版本和，说人话就是扫描线。

历史版本和是显然的，在向量上加一个维度就可以了，这里不在细说，代码根据矩形特征仍可以约去一大堆没用的信息。

我们还有构造双半群的做法，不过我不会 www。

代码如下：

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define pir pair<int,int>
using namespace std;
constexpr int MN=5e5+15;
int T,n,q,top1,top2,a[MN],b[MN],s1[MN],s2[MN];
ull ans[MN];
vector<pir> qry[MN];

struct Segment{
#define ls p<<1
#define rs p<<1|1
    struct{
        ull l,r,hsum,sum,suma,sumb,adda,addb,hadda,haddb,haddab,hcnt;
    }t[MN<<2];

    void doadd(int p,int va,int vb){
        t[p].sum+=t[p].sumb*va;
        t[p].suma+=(t[p].r-t[p].l+1)*va;
        t[p].adda+=va;
        t[p].sum+=t[p].suma*vb;
        t[p].sumb+=(t[p].r-t[p].l+1)*vb;
        t[p].addb+=vb;
    }

    void dohadd(int p,int cnt,int va,int vb,int vab){
        t[p].hsum+=t[p].sum*cnt+t[p].suma*vb+t[p].sumb*va+vab*(t[p].r-t[p].l+1);
        t[p].hcnt+=cnt;
        t[p].hadda+=t[p].adda*cnt+va;
        t[p].haddb+=t[p].addb*cnt+vb;
        t[p].haddab+=t[p].adda*t[p].addb*cnt+t[p].adda*vb+t[p].addb*va+vab;
    }

    void pushup(int p){
        t[p].sum=t[ls].sum+t[rs].sum;
        t[p].suma=t[ls].suma+t[rs].suma;
        t[p].sumb=t[ls].sumb+t[rs].sumb;
        t[p].hsum=t[ls].hsum+t[rs].hsum;
    }

    void pushdown(int p){
        dohadd(ls,t[p].hcnt,t[p].hadda,t[p].haddb,t[p].haddab);
        dohadd(rs,t[p].hcnt,t[p].hadda,t[p].haddb,t[p].haddab);
        doadd(ls,t[p].adda,t[p].addb);
        doadd(rs,t[p].adda,t[p].addb);
        t[p].adda=t[p].addb=t[p].hadda=t[p].haddb=t[p].haddab=t[p].hcnt=0;
    }

    void build(int p,int l,int r){
        t[p].l=l;
        t[p].r=r;
        if(l==r) return;
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
    }

    void modifya(int p,int fl,int fr,int k){
        if(t[p].l>=fl&&t[p].r<=fr){
            doadd(p,k,0);
            return;
        }
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(mid>=fl) modifya(ls,fl,fr,k);
        if(mid<fr) modifya(rs,fl,fr,k);
        pushup(p);
    }

    void modifyb(int p,int fl,int fr,int k){
        if(t[p].l>=fl&&t[p].r<=fr){
            doadd(p,0,k);
            return;
        }
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(mid>=fl) modifyb(ls,fl,fr,k);
        if(mid<fr) modifyb(rs,fl,fr,k);
        pushup(p);
        
    }

    int query(int p,int fl,int fr){
        if(t[p].l>=fl&&t[p].r<=fr){
            return t[p].hsum;
        }
        pushdown(p);
        int ret=0,mid=(t[p].l+t[p].r)>>1;
        if(mid>=fl) ret+=query(ls,fl,fr);
        if(mid<fr) ret+=query(rs,fl,fr);
        return ret;
    }

    void upd(){
        dohadd(1,1,0,0,0);
    }

#undef ls
#undef rs
}sg;


signed main(){
    cin>>T>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    cin>>q;
    for(int i=1;i<=q;i++){
        int l,r;
        cin>>l>>r;
        qry[r].push_back(pir(l,i));
    }
    sg.build(1,1,n);
    for(int i=1;i<=n;i++){
        while(top1&&a[i]>a[s1[top1]]){
            sg.modifya(1,s1[top1-1]+1,s1[top1],-a[s1[top1]]);
            top1--;
        }
        sg.modifya(1,s1[top1]+1,i,a[i]);
        while(top2&&b[i]>b[s2[top2]]){
            sg.modifyb(1,s2[top2-1]+1,s2[top2],-b[s2[top2]]);
            top2--;
        }
        sg.modifyb(1,s2[top2]+1,i,b[i]);
        sg.upd();
        s1[++top1]=i;
        s2[++top2]=i;
        for(auto p:qry[i]){
            ans[p.second]=sg.query(1,p.first,i);
        }
    }
    for(int i=1;i<=q;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}

3. 特殊线段树

有一类线段树不能简单归类到半群和环线段树，但是通常底层的信息维护都具有一定的相通性。

3.1 平衡树

平衡树就是支持插入的线段树。

啊？

3.2 吉司机线段树

这里吉司机可以去网上搜索教程，这里不在叙述。

那么吉司机和环线段树的相通之处，在于环结构需要多维护一个 “仅最小值加 $x$ ” 的操作，然后寻找修改区间这部分的算法有所改变。所以很多“环线段树”
的方法还是可用的。

3.3 底层分块

底层分块是一个线段树优化空间的技巧，大致思想就是线段树的叶子节点是 $O(\log n)$ 而不是 $O(1)$ 的区间长度，那么节点数量就减少到了 $O(\dfrac{n}{\log n})$ ，而修改查询的时间复杂度仍然是 $O(\log n)$ 的。

这种修改在有很多个线段树，但是储存的底层下标不交的时候有很好的优化效果，例如魔鬼题 [Ynoi2007] rgxsxrs。

这种结构我们只是认为它的结构发生了改变，而底层信息在维护的时候是没有太大变化的，和环线段树差不太多。

4. 后言

抽象化不是为了变难，而是为了变得更加简便，方便与实践。

“在数学中，进步往往来自于更深刻的抽象，而不是更复杂的计算” ——Alexander Grothendieck

通过抽象化，我们能够总结出线段树解题的一般步骤，以及各个线段树维护复杂信息的一般性与特殊性。

感觉学到很多，故作学习笔记，以摸鱼。

开始时间：2025/7/23 18:34
结束时间：2025/7/23 20:36
字数：5209 字。

参考

Alex_wei 的线段树进阶
神秘课件

数据结构

#线段树

线段树理论笔记

https://worldcpu.github.io/posts/dba6cc97/

作者

wjyppm

发布于

2025年7月23日

更新于

2025年7月24日

许可协议

agc056b题解上一篇

Hall定理下一篇