线段树与矩阵

技术分享 1年前 (2025-01-24) 0 999+

线段树

线段树的双半群模型

线段树上每个节点都有数据与标记两种信息，称作 (D) 与 (T)。

则需要存在 (D*D=D^prime) 的转移，即数据合并。
以及 (D*T=D^prime), 即标记转移。
以及 (T*T=T^{prime}), 即标记合并。

同时还需要满足结合律与分配律，这是一个半群，再存在一个单位元 (epsilon) ,使(T*epsilon=epsilon*T=T) 则为幺半群。则我们可以维护两个结构体，将三种转移加入即可。
这里举个例子。
区间加，区间乘，区间查询。则有(D={l,s}) , (T={a,b}) 。
则有 ((l_1,s_1)*(l_2,s_2)=(l_1+l_2,s_1+s_2))。
以及 ((l,s)*(a,b)=(l,as+lb))。
以及 ((a_1,b_1)*(a_2,b_2)=(a_1a_2,b_1a_2+b_2))。

显然，这些东西都是可以用矩阵维护的。

矩阵乘法与线段树标记

区间加法线段树

考虑每一个区间维护一个向量 (vec{a}:)

[vec{a}=begin{bmatrix}sum\lenend{bmatrix} ]

我们对于这个区间加上某一个数的操作可以看作左乘一个矩阵：

[begin{bmatrix}sum+ctimes len\lenend{bmatrix}=begin{bmatrix}1&c\0&1end{bmatrix}begin{bmatrix}sum\lenend{bmatrix} ]

此时，我们只需要维护左乘矩阵即可。

这里可以解释为什么只需要一个懒标记标记维护区间加信息。
考虑到左乘的是一个上三角矩阵，而可以证明上三角乘上三角还是上三角，并且在这个情景中，只有右上角的位置数值会变化，于是只需要用一个标记维护右上角的值即可，也就是我们平时维护的那个懒标记。

线段树历史版本和

假设只有区间加操作。
每一个区间维护一个向量 (vec{a}:)

[vec{a}=begin{bmatrix}his\sum\lenend{bmatrix} ]

其中 (his) 表示历史版本和，(sum) 表示当前区间和，(len) 是区间长度。

对于区间加的操作左乘矩阵没有什么变化。

但是我们多了令 (hisleftarrow his+sum) 的操作，考虑利用矩阵表示：

[begin{bmatrix}his+sum\sum\lenend{bmatrix}=begin{bmatrix}1&1&0\0&1&0\0&0&1end{bmatrix}begin{bmatrix}his\sum\lenend{bmatrix} ]

还是维护左乘矩阵即可。

线段树历史最值

广义矩阵

两个矩阵 (A_{i, k}, B_{k, j}) 相乘得到 (C_{i, j}) ，满足 (C_{i, j}=sum A_{i, k} B_{k, j}) 。
而处理区间最值和历史最值时，常用广义矩乘，即 (C_{i, j}=max left(A_{i, k}+B_{k, j}right)) 。

这里，我们只要维护,(+ max) 两种运算，它们满足

交换律：(a+b=b+a, max (a, b)=max (b, a)) 。
结合律：((a+b)+c=a+(b+c), max (max (a, b), c)=max (a, max (b, c))) 。
单位元：(a+0=0+a=a, max (a,-infty)=max (-infty, a)=a) 。
加法逆元（相反数）：(a+(-a)=(-a)+a=0) 。
分配律：(a+max (b, c)=max (a+b, a+c), max (a, b)+c=max (a+c, b+c)) 。

广义矩阵乘法显然具有结合律。

区间历史最值维护。

考虑序列每一个数维护一个向量 (left[begin{array}{l}a_i \ b_iend{array}right], ~ a_i) 表示当前值，(b_i) 表示历史最值，用线段树维护区间向量和（即 (a_i, b_i) 的最大值）。
那么区间加 (k) 可以看作 (left[begin{array}{l}a \ bend{array}right] leftarrowleft[begin{array}{c}a+k \ max {b, a+k}end{array}right]) ，可以很容易地构造广义矩阵乘法： (begin{bmatrix} k & -infty \ k & 0 end{bmatrix} begin{bmatrix} a \ b end{bmatrix}=left[begin{array}{c}a+k \ max {b, a+k}end{array}right]) ，故可以将懒标记设为 (begin{bmatrix} k & -infty \ k & 0 end{bmatrix}) 这个矩阵。

例题：P4314 CPU 监控 - 洛谷 | 计算机科学教育新生态

本题需要支持区间赋值。（这个操作可以转化为区间加，就是即使线段树节点被区间完包，只要最大值不等于最小值，就递归下去，根据颜色段均雊理论，这部分的均摊时间复杂度为 (O(n)) ）。
可以给向量再加—维，使其变为 (left[begin{array}{l}a \ b \ 0end{array}right]) ，这样就有 (left[begin{array}{ccc} -infty & -infty & k \ -infty & 0 & k \ -infty & -infty & 0 end{array}right]left[begin{array}{l} a \ b \ 0 end{array}right]=left[begin{array}{c} k \ max {b, k} \ 0 end{array}right])。

将矩阵转为标记

在普通的历史最值维护中，我们可以注意到：

(begin{bmatrix}a&-infty\b&0end{bmatrix}+begin{bmatrix}c&-infty\d&0end{bmatrix}=begin{bmatrix}max(a,c)&-infty\max(b,d)&0end{bmatrix}\begin{bmatrix}a&-infty\b&0end{bmatrix}begin{bmatrix}c&-infty\d&0end{bmatrix}=begin{bmatrix}a+c&-infty\max(b+c,d)&0end{bmatrix})

左乘矩阵的第二列的值始终不变，只有第一列的值在变化，故维护矩阵第一列的值即可。

事实上，左乘矩阵第一列的两个值分别对应论文中的 “加减标记” 和 “历史最大加减标记”。

例题：P6242 【模板】线段树 3（区间最值操作、区间历史最值） - 洛谷 | 计算机科学教育新生态

先不考虑历史最值问题。

考虑到区间取 (min) 的操作只会对最大值不超过 (k) 的节点产生影响，我们可以在这方面产生思路。为了使复杂度变对，线段树的一个节点要维护三个信息：区间最大值 (mx), 区间严格次大值 (se) 和最大值的个数 (cnt)。那么，一次区间最值操作作用在这个节点上时，可以被分为以下三种情况：

(kgeq mx), 此时该操作不会对当前节点产生影响，直接退出；
(se<k<mx), 此时这个节点维护的区间中所有最大值都会被修改为(k),而最大值个数不变。将
区间和加上 (cnttimes (k-mx)) ,打上懒标记，然后退出即可；
(kleq se), 此时无法快速更新区间信息，因此我们需要继续递归到左右子树中，回溯时合并信息。

原论文的证明告诉我们在没有修改操作时复杂度为 (O(mlog n)) 的。

由于区间加减操作，某些节点的值域会增大。论文里给的时间复杂度是 (O(mlog^2n)) 。而实际实现时会发现这个上界其实往往是跑不满的，速度几乎与大常数一个 (log) 接近。

此时，返回原题。我们将本题划分值域为最大值与非最大值，分别维护信息与 (tag)。

此处的矩阵只能分别简化最大值与非最大值的历史最值变化过程。在广义矩阵下并不能直接维护 (sum)，同时次大值以及最大值个数的记录也需要单独记录。本题更好的方法是直接用 (tag) 转移（本人不会完全使用矩阵完成这道题）。

const int N = 5e5 + 5; struct SGT {     ll sum;     int maxa, maxb, cnt, se;     int add1, add2, hadd1, hadd2; // 最大值/非最大值的标记 最大值/非最大值的历史最大标记 } tr[N << 2]; #define ls (id << 1) #define rs (id << 1 | 1) #define mid (l + r >> 1) il void pushup(int id) {     tr[id].sum = tr[ls].sum + tr[rs].sum;     tr[id].maxa = max(tr[ls].maxa, tr[rs].maxa);     tr[id].maxb = max(tr[ls].maxb, tr[rs].maxb);     if (tr[ls].maxa == tr[rs].maxa) {         tr[id].se = max(tr[ls].se, tr[rs].se);         tr[id].cnt = tr[ls].cnt + tr[rs].cnt;     } else if (tr[ls].maxa > tr[rs].maxa) {         tr[id].se = max(tr[ls].se, tr[rs].maxa);         tr[id].cnt = tr[ls].cnt;     } else {         tr[id].se = max(tr[ls].maxa, tr[rs].se);         tr[id].cnt = tr[rs].cnt;     } } void build(int l, int r, int id) {     if (l == r) {         int x; read(x); tr[id].add1 = tr[id].add2 = tr[id].hadd1 = tr[id].hadd2 = 0;         return tr[id].sum = tr[id].maxa = tr[id].maxb = x, tr[id].se = -2e9, tr[id].cnt = 1, void();     }     build(l, mid, ls), build(mid + 1, r, rs);     pushup(id); } il void work(int tag1, int tag2, int htag1, int htag2, int l, int r, int id) {     tr[id].sum += 1ll * tag1 * tr[id].cnt + 1ll * tag2 * (r - l + 1 - tr[id].cnt);     tr[id].maxb = max(tr[id].maxb, tr[id].maxa + htag1); tr[id].maxa += tag1;      if (tr[id].se != -2e9) tr[id].se += tag2;     tr[id].hadd1 = max(tr[id].hadd1, tr[id].add1 + htag1);     tr[id].hadd2 = max(tr[id].hadd2, tr[id].add2 + htag2);     tr[id].add1 += tag1, tr[id].add2 += tag2; } il void pushdown(int l, int r, int id) {     int mx = max(tr[ls].maxa, tr[rs].maxa);     if (tr[ls].maxa == mx) work(tr[id].add1, tr[id].add2, tr[id].hadd1, tr[id].hadd2, l, mid, ls);     else work(tr[id].add2, tr[id].add2, tr[id].hadd2, tr[id].hadd2, l, mid, ls);     if (tr[rs].maxa == mx) work(tr[id].add1, tr[id].add2, tr[id].hadd1, tr[id].hadd2, mid + 1, r, rs);     else work(tr[id].add2, tr[id].add2, tr[id].hadd2, tr[id].hadd2, mid + 1, r, rs);     tr[id].add1 = tr[id].add2 = tr[id].hadd1 = tr[id].hadd2 = 0; } il void add(int l, int r, int x, int y, int k, int id) {     if (l > y || r < x) return ;     if (l >= x && r <= y) {         tr[id].sum += 1LL * k * (r - l + 1);         tr[id].maxa += k; tr[id].maxb = max(tr[id].maxb, tr[id].maxa);         if (tr[id].se != -2e9) tr[id].se += k;         tr[id].add1 += k, tr[id].add2 += k;         tr[id].hadd1 = max(tr[id].hadd1, tr[id].add1);         tr[id].hadd2 = max(tr[id].hadd1, tr[id].add2);         return ;     }     pushdown(l, r, id);     add(l, mid, x, y, k, ls), add(mid + 1, r, x, y, k, rs);     pushup(id); } il void mdf(int l, int r, int x, int y, int k, int id) {     if (l > y || r < x || tr[id].maxa <= k) return ;     if (l >= x && r <= y && tr[id].se < k) {         int t = tr[id].maxa - k;         tr[id].sum -= 1LL * tr[id].cnt * t;         tr[id].maxa = k, tr[id].add1 -= t;         return ;     }     pushdown(l, r, id);     mdf(l, mid, x, y, k, ls), mdf(mid + 1, r, x, y, k, rs);     pushup(id); } il ll qry_sum(int l, int r, int x, int y, int id) {     if (l > y || r < x) return 0;     if (l >= x && r <= y) return tr[id].sum;     pushdown(l, r, id);     return qry_sum(l, mid, x, y, ls) + qry_sum(mid + 1, r, x, y, rs); } il ll qry_a(int l, int r, int x, int y, int id) {     if (l > y || r < x) return -2e9;     if (l >= x && r <= y) return tr[id].maxa;     pushdown(l, r, id);     return max(qry_a(l, mid, x, y, ls), qry_a(mid + 1, r, x, y, rs)); } il ll qry_b(int l, int r, int x, int y, int id) {     if (l > y || r < x) return -2e9;     if (l >= x && r <= y) return tr[id].maxb;     pushdown(l, r, id);     return max(qry_b(l, mid, x, y, ls), qry_b(mid + 1, r, x, y, rs)); } int n, m; signed main() {     read(n, m);     build(1, n, 1);     while (m--) {         int op, l, r, k;         read(op, l, r);         if (op == 1) read(k), add(1, n, l, r, k, 1);         else if (op == 2) read(k), mdf(1, n, l, r, k, 1);         else if (op == 3) write(qry_sum(1, n, l, r, 1)), ptc('n');         else if (op == 4) write(qry_a(1, n, l, r, 1)), ptc('n');         else if (op == 5) write(qry_b(1, n, l, r, 1)), ptc('n');     }     return 0; }

我始终认为这种题看代码是最好的理解方式。

普通矩阵乘法与区间历史和

例题：P8868[NOIP2022] 比赛

我们离线所有询问，对右端点(r)进行扫描线。

在扫描过程中，我们设 (X_l) 和 (Y_l) 分别表示 (l,ldots,r) 范围内 (A_i) 和 (B_i) 的最大值。

我们可以在扫描的时候，对每个(l),维护

[S_{l,r}=sum_{r'=l}^rX_{l,r'}times Y_{l,r'}. ]

这样的话，我们要查询的就是 (lsim r) 的区间 (S) 和。

而我们的操作则是区间 (X) 修改 (覆盖),区间 (Y) 修改 (覆盖), 以及 (Sleftarrow S+Xtimes Y)。

至此，本题转为了区间覆盖，区间历史和问题。

维护向量：

[vec{a}=begin{bmatrix}his\ab\a\b\lenend{bmatrix} ]

其中 (his) 表示历史版本和，(ab) 表示 ((sum A_i)times(sum B_i)), (a,b) 分别表示 (sum A_i,sum B_i)。
于是，对于 (A) 的区间加操作可以表示为：

[begin{bmatrix}his\ab+xtimes b\a+xtimes len\b\lenend{bmatrix}=begin{bmatrix}1&0&0&0&0\0&1&0&x&0\0&0&1&0&x\0&0&0&1&0\0&0&0&0&1end{bmatrix}begin{bmatrix}his\ab\a\b\lenend{bmatrix} ]

对 (B) 的操作同理。

刷新历史和的操作可以表示为：

[begin{bmatrix}his+ab\ab\a\b\lenend{bmatrix}=begin{bmatrix}1&1&0&0&0\0&1&0&0&0\0&0&1&0&0\0&0&0&1&0\0&0&0&0&1end{bmatrix}begin{bmatrix}his\ab\a\b\lenend{bmatrix} ]

维护左乘矩阵即可。复杂度 (O(k^3nlog n))，可以获得 (76) 分。在卡常和乘法展开后也许可以获得满分。

优化标记常数

就像前面提到的，矩阵中总有很多信息始终不变，那么这些信息理论是不必要记录的。

我们以如下乘法为例：

[begin{bmatrix}his+sum\sum\lenend{bmatrix}=begin{bmatrix}1&1&0\0&1&0\0&0&1end{bmatrix}begin{bmatrix}his\sum\lenend{bmatrix} ]

操作的矩阵有两种：

[begin{bmatrix}1&1&0\0&1&0\0&0&1end{bmatrix},begin{bmatrix}1&0&0\0&1&x\0&0&1end{bmatrix} ]

也就意味着我们只需要关注形如：

[begin{bmatrix}1&a&0\0&1&b\0&0&1end{bmatrix}begin{bmatrix}1&c&0\0&1&d\0&0&1end{bmatrix}=begin{bmatrix}1&c+a&ad\0&1&b+b\0&0&1end{bmatrix} ]

于是意味着我们只需要维护右上角的三个位置，每次按照上式直接修改即可，这样常数大大减少，与维护一堆tag的常数一致了。

然而发现事实上右上角都会有值，于是重新修正：

[begin{bmatrix}1&a&b\0&1&c\0&0&1end{bmatrix}begin{bmatrix}1&d&e\0&1&f\0&0&1end{bmatrix}=begin{bmatrix}1&a+d&e+af+b\0&1&c+f\0&0&1end{bmatrix} ]

这意味着我们只需要维护右上角的三个位置，每次按照上式直接修改即可，这样常数大大减少。

同理，对于P8868[NOIP2022] 比赛，发现有用的位置只有 (9) 个，维护这 (9) 个位置即可。

如果不好观察，不妨给矩阵随机赋值，打表出不变的位置即可。

关于向量构造的一些小技巧

一般来说，我们需要构造出来的向量，对于每一个操作都应该是一个上/下三角矩阵的形式，这样更加方便我们观察，理解，优化。
而如果要成为一个上三角，就意味着对于 (vec{a}_i) 只会由 (j>i,vec{a}_j) 转移而来。
于是一般来说，会将不变的长度放在最下面，将历史版本信息放在最上面，一般的信息则放在中间。