标记永久化

也就是没有 push_down

注意前面两个问题是具有启发性的，不要略去不看

区间加，单点和

每个节点 \(u\) 额外维护一个 add 值，表示 \(u\) 所代表的区间的总增加量

此时只考虑该区间的增加情况，不用考虑它祖先或者儿子的增加情况

这样做的代价是查询时把没考虑的祖先 以及 儿子 的增加情况考虑进去

区间加：把 \(\log n\) 个点的 add 加一下

单点和：对于一个单点，所有包含它的区间的 add 都对他有贡献

于是把经过的节点的 add 累加起来回答

区间加，区间和

对当前区间 \(u\)，可以想到维护两个信息：

• \(u\) 的区间和 \(sum(u)\)
• \(u\) 的增加量 \(add(u)\)

但是这两个标记是如何具体地维护从而支持区间加、区间和的呢？我们不知道

注意首先要想求出 \(u\) 的答案，我们需要考虑除了 \(u\) 本身被修改的影响之外的两个影响：

• \(u\) 的儿子对 \(u\) 答案的影响
• \(u\) 的祖先对 \(u\) 答案的影响

容易想到让 \(u\) 的标记维护第一个影响，然后在查询的时候对答案考虑第二个影响（查询时路过的节点都是当前查询节点的祖先，而 push_up 就相当于用儿子更新 \(u\)）

而由于询问时对于一个祖先需要方便地算出它对它的子树的影响，于是我们令 \(add(u)\) 表示 \(u\) 整个区间所有数都同步累加的增加量

此时 query 的祖先的影响就容易维护了，而 update 对该标记的影响也就是对所操作区间的 \(add\) 累加.

而由于节点内部需要记录所有儿子对 \(u\) 的影响，所以令 \(sum(u)\) 为考虑 \(u\) 子树内所有儿子对 \(u\) 影响的区间和

此时对于 \(sum\) 有两种维护方法：

• 一种方法：

  考虑通过 push_up 更新儿子对 \(u\) 的影响

  假设此时儿子的信息都已经搞定，也就是儿子的 \(sum\) 已经考虑了儿子及其子树的修改情况，现在我们需要用儿子的信息更新 \(u\) 的信息

  直接 \(sum(u)=sum(lc)+sum(rc)\) 即可

  而对于当前修改节点，修改 \(sum\) 即可

• 一种方法：

  update 时顺带把路过的节点的 \(sum\) 更新了，因为路过的节点一定是当前修改的节点的祖先，这次 update 一定影响到了这些点的区间和

注意虽然这两种方法的思想不同，一种是在回溯时更新，一种是在递归过程中更新，但是代码差异很小，同时这里建议写 push_up

然后在 query 时直接用 \(sum(u)\) 即可

所以 \(sum\) 这个标记是只考虑 \(u\) 这个单独的区间的内部情况的，也就是只考虑了 \(u\) 以及 其子树所有的修改情况，没有考虑其祖先的修改对它的影响

于是我们就推导出了标记永久化的过程.

总结：

注意这个问题中区间 \(u\) 维护了如下两个信息：

• 考虑 \(u\) 子树内的所有修改（增加）情况，\(u\) 的区间和 \(sum(u)\)
• 考虑 \(u\) 作为祖先，它的修改（增加）对儿子的答案的贡献 \(add(u)\)

更形象地，\(sum(u)\) 的范围是 \(u\) 的整棵子树，而 \(add(u)\) 的范围是 \(u\) 这一个节点，对儿子的答案的贡献

这种标记维护方式就是标记永久化的核心思想.

而这个方法的必要性和充分性都在前面的一步步推导中体现了.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 1e5 + 10;
ll sum[N << 2], add[N << 2];
int n, m;

#define lc (u << 1)
#define rc ((u << 1) | 1)
#define mid ((l + r) >> 1)

void Up(int u, int l, int r) { sum[u] = sum[lc] + sum[rc] + 1ll * (r - l + 1) * add[u]; }
void build(int u, int l, int r) {
    if (l == r) return cin >> sum[u], void();
    build(lc, l, mid), build(rc, mid + 1, r), Up(u, l, r);
}
void Upd(int u, int l, int r, int x, int y, ll v) {
    if (y < l || r < x) return;
    if (x <= l && r <= y) return add[u] += v, sum[u] += 1ll * (r - l + 1) * v, void();
    Upd(lc, l, mid, x, y, v), Upd(rc, mid + 1, r, x, y, v), Up(u, l, r);
}
ll Qry(int u, int l, int r, int x, int y) {
    if (y < l || r < x) return 0ll;
    if (x <= l && r <= y) return sum[u];
    return Qry(lc, l, mid, x, y) + Qry(rc, mid + 1, r, x, y) + 1ll * (min(y, r) - max(x, l) + 1) * add[u];
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n >> m, build(1, 1, n);
    while (m--) {
        int op;
        cin >> op;
        if (op == 2) {
            int l, r;
            cin >> l >> r;
            cout << Qry(1, 1, n, l, r) << "\n";
        } else {
            int l, r; ll c;
            cin >> l >> r >> c;
            Upd(1, 1, n, l, r, c);
        }
    }
}

修改时改一路上的 sum、完全包含的 tag
查询时加一路上的 tag、完全包含的 sum

区间赋值、单点查询

假设前面两节你都看懂了

发现从上往下合并标记的时候有困难：如何合并？

发现只要保留最晚的赋值标记就可以

于是再维护一个时间戳，表示这个赋值标记的时间，合并时保留最晚的标记

区间加、区间赋值、区间和

维护 \(sum,add,tag,time\)，\(add\) 和 \(tag\) 任意时刻总是保留其一

区间加：若有 \(tag\)，\(tag\gets tag+x,time\gets now\)；否则 \(add\gets add+x\)

区间赋值：\(tag\gets x,time\gets now\)

区间和：合并标记时 \(add\) 和 \(tag\) 保留其一

• 有 \(tag\)：若当前节点有 \(tag\) 保留最晚的 \(tag\)，否则 \(tag\gets tag+add_u\)
• 无 \(tag\)：若当前节点有 \(tag\) 则 \(tag\gets tag_u+add,add\gets0\)，否则 \(add\gets add+add_u\)

算答案时类似

区间整除、区间加、区间和

标记 \((a,b)\) 表示先加 \(a\) 再除以 \(b\)，记 \(*\) 为标记合并

区间加：\(\left\lfloor\dfrac{x+a}b\right\rfloor+p=\left\lfloor\dfrac{x+a+bp}b\right\rfloor\)

区间整除：\(\left\lfloor\dfrac{\left\lfloor\frac{x+a}b\right\rfloor}p\right\rfloor=\left\lfloor\dfrac{x+a}{bp}\right\rfloor\)

这就说明了 \((a,b)*(c,d)=(a+bc,bd)\)，没有交换律

网上有个说法是若能找到一个 \(a'\) 使得 \(a*b=b*a'\)，就可以做

具体是强制让儿子的标记比父亲的标记晚

但是这样不可行，复杂度是错的

于是这道题可以普通线段树做

区间加、区间和、区间和历史最大值

标记 \((a,b,c)\) 表示该区间加了 \(a\)，区间和为 \(b\)，区间和历史最大值为 \(c\)

区间加：\((a,b,c)\to(a+p,b+(r-l+1)\cdot p,\max(c,b+(r-l+1)\cdot p))\)

这是可以标记永久化的

区间 checkmax、区间 max、单点查

标记 \((a,b)\) 表示 checkmax 了 \(a\)，当前区间 \(\max=b\)

区间 checkmax：\((a,b)\to(\max(a,x),\max(b,x))\)

这也可以方便的标记永久化

区间加、区间乘、区间和

标记 \((a,b,c)\) 表示加、乘、和，钦定先乘再加（即 \(x\) 的真实值为 \(ax+b\)）

区间加：\((a,b,c)\to(a+x,b,c+x)\)

区间乘：\((a,b,c)\to(ax,bx,cx)\)

所以 \((a,b,c)*(d,e)=(ae+d,be,ce+d)\)

可以普通线段树做

不具有交换律的标记如何维护？

一个通用做法是：对每个标记维护时间戳

从根节点走到当前节点一共经过了 \(\log n\) 个标记

用 set 维护从根节点到当前点的所有标记，是按时间从早到晚排序

到达相应节点后再把 set 上的标记一个个合并

时间复杂度 \(\mathcal O(n\log^2n)\)

因为它就是普通线段树区间查询再乘了个 set 的 log

而且实际上遍历 set 是 \(\mathcal O(n)\) 的，\(n\) 为 set 内元素个数

我原来以为它是 3 个 log 的……