树状数组 & 线段树的其他用法

Wonder_Fish · 2025-04-29 17:21:28 · 算法·理论

cnblogs

[2025-06-23] 加入树状数组的内容，整理完成。

树状数组二分

树状数组二分可以抽象成这样一类问题：存在分割点 q，使得 \leq q 的位置满足某个限制，而 > q 的位置不满足该限制，求 q。

从大到小考虑 1\leq 2^k \leq n，每次尝试将 p 加上 2^k，由于从大到小枚举，根据树状数组的结构，c_{p+2^k} 存的值即为 \sum_{i=p+1}^{p+2^k} a_i，所以直接加上这个值判断一下，若满足就 p\leftarrow p+2^k,s\leftarrow s+c_{p+2^k}，否则不动，然后继续枚举。其实就是一个倍增。

但是树状数组二分只适用于在整个树状数组上二分，如果是局部，就没办法利用树状数组的结构了。~~所以还是需要树状数组 + 二分~~

P6619

原本是树状数组二分的模板题，但是用树状数组 + 二分水过去了。

其实就是要求冰火两方消耗能量较少的 2 倍，所以要让这个最小值最大。

发现其实冰系战士消耗的能量关于温度是一个上升的斜线（本质上是一个前缀和），火系下降（本质上是一个后缀和）。

所以它们的最小值最大应该是在交点处。但线不连续，所以要找两个位置，一个是最后一个 sf_i\geq sc_i 的位置，一个是第一个 sc_i>sf_i 的位置，很显然的二分。带修所以树状数组维护前缀和。

这样二分是在整个树状数组上的，根据树状数组的结构可以用类似倍增的方式 O(\log n) 过去。~~而不需要 O(\log ^2 n) 的树状数组 + 二分~~

P4602

整体二分 + 树状数组二分

P3586

似乎并不需要树状数组二分。

这题主要难在结论的推导，推出性质之后似乎就是一个简单的离线维护了。

二维树状数组

就是把一维的树状数组扩展一下，位置 (x,y) 存横坐标 (x-\operatorname{lowbit}(x),x]，纵坐标 (y-\operatorname{lowbit}(y),y] 的信息，支持单点修改区间查询且信息具有可减性的二维数点，或单点修改前缀查询的二维数点。

放一个二维树状数组的代码：

struct BIT{
    int s[maxn][maxn];
    void add(int x,int y,int z){
        for(int i=x;i<=n;i+=lowbit(i))
            for(int j=y;j<=m;j+=lowbit(j)) s[i][j]+=z;
        return ;
    }
    int ask(int x,int y){
        int res=0;
        for(int i=x;i;i-=lowbit(i))
            for(int j=y;j;j-=lowbit(j)) res+=s[i][j];
        return res;
    }
};

P4514

二维树状数组的模板。

二维树状数组维护二维前缀和。

设 (i,j) 差分数组为 d_{i,j},s_{i,j} 表示 (i,j) 的二维前缀和

s_{x,y}=\sum_{i=1}^x \sum_{j=1}^y a_{i,j}

=\sum_{i=1}^x \sum_{j=1}^y \sum_{k=1}^i \sum_{l=1}^j d_{k,l}

=\sum_{i=1}^x \sum_{j=1}^y d_{i,j} \cdot (x-i+1)\cdot(y-j+1)

=\sum_{i=1}^x \sum_{j=1}^y d_{i,j} (xy-xj+x-yi+ij-i+y-j+1)

=\sum_{i=1}^x \sum_{j=1}^y d_{i,j} [(xy+x+y+1)-i(y+1)-j(x+1)+ij]

所以维护 d_{i,j},d_{i,j} \cdot i,d_{i,j} \cdot j,d_{i,j}\cdot ij 四个二维树状数组就可以了。。

一维的高阶前缀和的推导方式类似，维护也是开好几个树状数组。

P1527

整体二分 + 二维树状数组 + 二维差分，不算太难。

对于可以 O(n^2) ，信息可减的二维数点，二维树状数组是一个很好的算法，不要去想什么主席树还是 kd-tree 还是树套树了。

可持久化线段树

需要查询历史版本的线段树。

注意到每次修改只会改动 O(\log n) 个位置，新建一个大小为 O(n) 的线段树非常浪费。考虑只新建修改的节点，未修改的部分直接指向原树上的节点，这样空间复杂度是 O(n+q\log n)，时间复杂度不变。

可以维护具有可减性的二维数点问题，或不具有可减性的，某一维是前缀，另一维随意的二维数点问题。

P2839

最大中位数有一个经典处理方法，二分答案 mid ，把 \geq mid 的设为 1 其它设为 -1，然后判断一段区间的和是否 \geq 0。（这句话我的等号是乱取的，实际上要根据题目考虑，这是细节）

这题对于询问二分答案，然后找到左端点右端点满足要求的最大子段和看看是否大于 0，这个最大子段和即 [b,c] 的和加上 [a,b-1] 的 lmx 加上 [c+1,d] 的 rmx。

可以用主席树维护，对于每一个值开一个主席树。

挺好的一道题。

P3293

考虑贪心，从高到低确定每一位。

需要判断每一位是否可以为 0 或 1，也就是支持在线查询 [l_i,r_i] 内是否有数的值在某个区间内，可持久化值域线段树维护。

P3402

并查集的信息都在 fa 和 sz 等数组上，用主席树维护 fa,sz 等并查集数组即可实现可持久化并查集，注意区分“可撤销并查集”。

P4768

一开始要做一个最短路的预处理，用 dij。（关于 SPFA，它死了）

如果不是强制在线（毒瘤出题人（恼），可以把询问离线下来用并查集。

那强制在线怎么办？用主席树存可持久化并查集，对每个水位都保存一个版本。

细节比较多。

P5283

可持久化 trie。为什么放这呢，因为可持久化的思路和线段树一模一样，并且 0-1 trie 就是一种非递归的权值线段树。

首先区间异或和转异或前缀和，然后问题变为找出前 k 大的 s_i \oplus s_j (j<i)，用堆维护。即先把对于每个 i 最小的上述东西放入一个堆，每次找到当前堆中最小值并删除，再向堆中加入这个最小值对应的 i 的下一个 s_i \oplus s_j。

虽然但是这题也有不用可持久化 trie 的做法，即不考虑 i>j 的限制会发现一个数对被算了两遍，那么就是找到前 2k 大的即可。没有 i>j 限制后一个 trie 即可解决。

线段树合并&分裂

啥？我学过？我忘了。

树套树

顾名思义，就是在树里面套一个树。

P3380

首先所有的查询都可以转化为查询一个区间中有多少数 \leq x，这是经典平衡树或值域线段树维护的东西，但是本题加上了区间限制，于是一棵平衡树就难以解决。

考虑到区间限制一般解决方式是线段树，所以就先开一棵线段树，线段树每个节点的信息再开一个平衡树。查询信息具有可加性，直接对线段树若干节点的平衡树求答案再加起来即可。

鉴于我不会写平衡树，总是把板子打错，所以在这里放一个 fhq-treap 基本操作的板子。哎，唐完了。

void pushup(int p){
    t[p].sz=t[t[p].l].sz+t[t[p].r].sz+1; //注意这里要加 1 算上自己，和线段树不一样
}
int add(int val){
    t[++tot].val=val; t[tot].dt=rand();
    t[tot].sz=1; return tot;
}
void split(int p,int val,int &x,int &y){
    if(!p){x=y=0; return ;} //有区间修改时先 pushdown 再分裂
    if(t[p].val<=val) x=p,split(t[x].r,val,t[x].r,y);
    else y=p,split(t[y].l,val,x,t[y].l);
    pushup(p); return ; //别忘了pushup
}
int merge(int x,int y){
    if(!x||!y) return x+y; //区间修改时这里 pushdown
    if(t[x].dt<t[y].dt){
        t[x].r=merge(t[x].r,y);
        pushup(x); return x;
    }
    else{
        t[y].l=merge(x,t[y].l);
        pushup(y); return y; //同样的，注意pushup
    }
    return 0;
}

平衡树也可以类似线段树一样维护复杂的区间修改区间查询如最大子段和等，功能较强大，空间常数略小，常在树套树中使用。

类似地，线段树套线段树（空间危），树状数组套平衡树，树状数组套树状数组也可以解决本题。

其实本质就是动态二维数点。

P3437

翻译一下就是，矩形 \max，矩形赋值。

区间 \max 区间赋值是线段树维护的问题，这题是二维的那就线段树套线段树。

代码有一些细节，使用了标记永久化。

线段树分治

用于解决形如“某东西（可能是边，点等）在时间 [l,r] 存在”的问题，其中维护这个东西不支持任意删除，但是可以撤回（常见的是并查集）。

考虑对时间轴建一棵线段树，然后按照线段树区间修改的方式在区间 [l,r] 对应的节点上加入这个东西。然后遍历这棵线段树，到达一个点的时候将点上存的修改加入，退出这点的时候将修改撤回。到达叶结点的时候处理询问，不难发现在叶结点时恰好加入对应时间的所有边。

P5787

判断二分图有两种方式：染色法和扩展域并查集。染色法涉及到整个图，不容易动态维护，所以考虑扩展域并查集。设 f_i,g_i 表示点 i 是左部点或是右部点。

在线段树上每条边出现的时间区间加上这条边，然后遍历这棵树。到达一个节点，首先记录当前操作栈的 top，然后将这个点上存的所有边尝试加入扩展域并查集。

具体地，对于边 (x,y)，若在加入这条边前，f_x,f_y 或 g_x,g_y 已经属于同一个集合，就表示 x,y 必须是同一边的点，那么加入这条边后，原图不再是二分图，直接将这个节点对应的区间全都输出 No 即可。

否则合并 f_x,g_y 和 g_x,f_y，表示若 x 是左部点，y 必须是右部点，反之同理。然后将这次操作的信息加入操作栈用于子树遍历完之后撤回。

并查集需要支持撤销所以不能路径压缩，要保证合并树的高度所以使用启发式合并（按照 size,dep 或者随机秩都可以）。

P4585

找某段区间内与一个数异或和最大的数是可持久化 trie 的经典问题。而本题多了一些时间的限制。

对两种商品分开处理。特殊商品不考虑时间段限制，是简单的，直接再开始的时候建出可持久化 trie，然后每个询问都查询一次即可。

对于普通商品，需要计算它对所有时间段包含它的时间的询问的贡献。考虑把所有询问时间段拆成线段树上的一些区间。那么对线段树的每个节点上挂着的询问会产生贡献的点，就是这个节点子树内所有有商品的叶结点。也就是每个有商品的叶节点会对它的 \log m 个祖先产生贡献。

把询问按区间查询的方式挂到线段树节点上，修改以单点修改的形式挂到所有路过的节点上，这样所有节点上的询问和修改的总数是 m\log m 级别的。对于每个节点，商品建立可持久化 trie，询问在上面查询，总复杂度是 O(m\log m\log V) 的。

CF938G

异或最短路是线性基基础问题，s\to t 的所有路径一定可以由任意一条路径异或上若干个环得到。并且对于异或任意环集合一定可以构造出一条合法路径使得路径异或和等于原路径异或环的异或和。一般来说都是先找出一棵生成树，然后用树上唯一路径作为开始的基础路径，然后依次加入非树边找到环（注意到环套环可以通过若干环的异或和表示出来）。

本题保证了任意时刻图连通所以不用担心无法到达的问题，也就是一定能找到一条上述基础路径。而现在要解决的问题就是查询基础路径的异或和和找到所有环。

首先线段树分治将所有操作转为加入和撤回，对于前者，需要动态维护一棵生成树和每个点到根的距离，启发式合并带权并查集即可。对于后者，加边的过程，线性基维护所有环，由于线性基很小，对于每层节点都开一个也没有问题，就不用撤销了。

据说类似题 P3733 有使用黑科技可删除线性基的在线做法，但是我不会了。

CF576E

半在线的线段树分治。若没有“只有当执行后仍然合法，才会执行本次操作”，这题就是 k 个线段树分治模板题。

首先将所有的操作变为在 [l,r] 时间内在颜色为 c 的图上加上边 (x,y)，然后由于要判断是否合法，合法才会对后面有影响，所以考虑将操作拆为 l 处的决定操作和 [l+1,r] 的延迟效果，然后在决定操作处判合法（所有决定操作都在叶结点上且每个叶结点只有一个），若合法再在线段树上 [l+1,r] 加入此操作，需要注意若它不合法，还需要延续上一个操作的效果。

由于分治的顺序是从左到右，所有操作的时间互不相同，每次叶子结点的修改只会对在其严格后面的操作有影响，因此修改不会涉及到已经分治过的结点。

CF1140F

本题难度不在分治而在维护上。

首先注意到一个性质：若两个点在同一列，那么它们各自的行的点列坐标集合相同，若在同一行同理。然后可以发现最后的形状一定是若干块，每行或列恰好属于一个块，块内的点数等于块中的行数乘列数。

而加入一个点，手动模拟一下发现相当于将它所在的行和列所在的块合并为一个块。那么就每行每列各看成一个点，用并查集维护块即可。

需要支持删除直接离线线段树分治转为撤销。

动态分治

瞎取的名字，来概括线段树维护某一类信息的题目，不是线段树分治。感觉分治和动态分治的关系类似于点分治和动态点分治（点分树）。

注意到大部分线段树能维护的信息需要满足：能快速对树上单个（叶）结点进行修改，快速合并区间贡献。

考虑其递归的过程，会发现特别像分治！分治是每次将一个大区间取 mid 为分界点划分为两个区间，然后计算左右区间内和跨过 mid 的三种贡献。那么把信息扔到线段树叶结点上，初整棵树始化一下就完成了整个分治过程。

把分治放在线段树上的好处是，它可以支持单点修改，也可以动态区间查询。不过区间查询和原来的分治略有区别，分治应该是对于一个区间只会合并一次，而线段树上查需要合并 \log 个区间。

感觉讲不清楚，具体看例题吧。

SP1716

经典题。

维护 mx,sum,lmx,rmx 分别表示当前区间内的最大子段和，区间和，左侧一段前缀的最大和，右侧一段后缀的最大和。合并的时候 mx,lmx,rmx 都可以分为过分界点和不过分界点，sum 直接加。

查询时候直接把包含的区间用上述方式拼起来即可。可以使用结构体重载运算符简化代码。

P6588

可以通过推式子转成区间和区间平方和等东西，但是那样太烦了！

注意到所有修改操作都是单点，可以全都看成单点赋值，也就是只要维护一些东西解决区间查询问题。

注意到两种查询操作都是和区间内所有点对 (i,j) (i<j) 有关，最终也就是要求区间所有 (i,j) 的 x_ix_j,x_iy_j,y_ix_j,y_iy_j 的和，维护区间 x,y 的和后，上述信息是非常容易合并的。

线段树维护一下，就做完了。

Segment Tree Beats

2016 年国家集训队论文

又名吉司机线段树。我不知道这个是怎么想出来的，感觉非常强，拜谢吉老师。我不是特别会证明，势能分析还是太强了，所以就直接说做法了，证明看论文吧。

吉司机线段树用于维护区间取 \min 或 \max 的操作，与求和，历史和等询问放在一起的题目。checkmin/checkmax 操作难以直接对区间和修改，除非该操作对区间无影响或区间所有数相同。

取 \max 和取 \min 是相似的，下面只讨论取 \min。

考虑将区间内的值分为两部分：最大值（所有值等于最大值的位置）和非最大值（除去最大值之外的位置），设最大值为 mx0，非最大值的最大值为 mx1。

修改时，设取 \min 的值为 v，若当前区间被修改区间完全包含：

1.v\geq mx0，不会产生影响，直接返回。

2.mx1< v<mx0，将所有最大值改为 v，打上标记后返回。

3.v\leq mx1，继续递归子树。

需要维护区间最大值个数和修改 tag。这样就把区间 checkmax 转化成区间加或区间赋值操作了，更容易与各种查询结合。

需要注意 pushdown 的时候需要讨论左右儿子的 mx0 到底对应当前根的 mx0 还是 mx1。细节较多。

这样的复杂度似乎是 \log^2 的？还是 \log 的？我不确定，但是它跑得和 \log 一样快。

P6242

对于最大值和非最大值分别维护 [hmx,mx]，然后所有的操作都是区间加，还需要维护历史最大值，所以维护 [htag,tag]，后者为加法 tag，前者为加法 tag 达到过的最大值，pushdown 的时候讨论一下，和可以带着维护。

上述 tag 的设计可以参考下一部分，即设计 (\max,+) 矩阵。

代码细节较多。

一开始有个疑问是为什么要维护非最大值的历史最大值，感觉最大值一直大于非最大值所以历史最大值在最大值处。

但是首先根据实际意义这不对，最大值位置会改变，历史最大值可能在当前的非最大值处，其次 pushdown 的时候可能需要 rt 的非最大值 tag 去更新 ls 和 rs 的最大值 tag。

P10639

同时出现了取 \min 和 \max。若是参考上一题的实现方式，应该是将区间分为三个部分，分别维护三个部分的 tag，但是这样对于只有一种数和只有两种数的区间修改和时需要讨论很多。

考虑换一种方式，维护全局，最大值和最小值部分的加法 tag，这样就避免了修改和时候的讨论。

对和的不同操作互不影响，但是要注意对于只有一种数的区间，修改最大/最小值会连带修改最小/最大值，对于只有两种数的区间则会影响次小/次大值，需要讨论一下。但是注意这样的连带修改只修改值，不会修改 tag。

代码细节较多。

UOJ515

这种对下标扫描线，维护时间信息是第一次见！孤陋寡闻了。

似乎可以直接上线段树合并分裂来维护，但是我不会线段树合并分裂。

考虑不带修如何求后缀 \min 个数。考虑从后向前扫整个数组，维护一个值 mn 表示当前后缀 \min，扫到第 i 位时，mn 对 a_i 取 \min。一个后缀 [i,n] 的不同后缀 \min 个数就是在这个过程中，扫到位置 i 时 mn 被有效更新的次数。

但是这题有对 a_i 的修改操作，可以看成在每个位置 i 时间分成若干段，每段 t\in [l_j,r_j] 时 a_i=v_j。考虑用线段树对每个时间维护上述 mn 即其被更新的次数，需要支持操作区间 checkmin 和计算每个位置被有效更新的次数。

但是这个更新次数并不是很好直接对区间维护，因为区间里面有很多不同的数，不知道具体哪些有效。考虑吉司机线段树，分开区间最大值和非最大值，每次只对最大值操作就好维护了。

时间复杂度 O(n\log n)，但是由于要卡掉一些别的做法所以时间开的非常紧，需要加上区间最大值 mx0 \leq val 时就返回的剪枝。我自带大常数被卡了好久。

P11368

考虑使用与上一题相同的方式维护前缀最大值，维护时间的线段树，对下标扫描线。

线段树需要支持：区间 checkmax，区间历史和，吉司机线段树维护即可。

需要卡常。所以我什么时候能不自带大常数啊。

矩阵维护节点信息和标记

有时候各种操作比较多，较难设计标记，也较难准确写出标记合并和标记对节点的贡献的转移，可以考虑使用矩阵辅助设计标记。

具体地，将每个节点的所有参数放在一起看成一个 k 维向量，然后使用一个 k\times k 的矩阵描述每个操作对节点参数的影响，这样标记合并就是两个 k\times k 的矩阵相乘，标记对节点的修改就用节点表示的向量乘标记矩阵，而节点信息的合并就是向量相加。

这里的矩乘可能是广义矩乘。