空间线性的线段树分治

· · 算法·理论

省流：下面有代码框架。

先看一个朴素做法。

仍然是线段树，每个节点开一个 vector。
对于每个区间修改，我们维护 l, r 和需要进行的修改，全都扔到根节点的 vector 里面。
然后 dfs 整棵树，到达节点 i 时，将包含整个区间的修改都做了，然后剩下的修改分别扔到左右子节点的 vector 即可。
最后先清空当前节点的 vector（需要释放内存），然后分别递归左右子树。

我们知道这一朴素做法的空间是 O(n \log n) 的。

Q：那和先把区间修改拆到 O(\log n) 个节点上的写法有什么区别呢？
A：随机数据下上述做法的空间复杂度是 O(n) 的。

关于证明，考虑每个区间都会被拆成一个前缀修改和一个后缀修改。
这里我们只考虑后缀修改即可。
考虑每次只有 \frac{1}{2} 的概率跨过 mid，跨过 mid 的时候才可能给左子树递归时贡献 1 的空间。
所以期望意义下一个后缀修改贡献的空间复杂度是 \sum \limits _{i \ge 1} \frac{1}{2^i} = O(1) 的。

关于 hack，全是 [2, n - 1] 就卡满了。

然后是常见的做法。
还是上述实现，但是把 dfs 改成 bfs
这个空间是 O(n) 的，也算是比较常见的写法了。

关于证明，考虑线段树进行区间修改的时候，同一个深度的节点至多访问 4 个。
因此同一深度下每个修改至多被拆成四份。
所以空间就是线性的。

你说得对但是写个 bfs 也太麻烦了。
这里介绍一种更简单的方法。

还是上述做法，对于一个节点，我们统计一下跨过 mid 的前后缀数量，分别记为 x, y。
若 x > y，那么我们先递归左子树后递归右子树。
若 x \le y，那就先递归右子树再递归左子树。

酱紫空间就是线性的了。贴个代码。 

void div(int a, int l, int r)
{
    if (l == r)
        return;
    int mid = (l + r) / 2, cnt1 = 0, cnt2 = 0;
    for (node i : vec[a])
        if (i.l <= l && r <= i.r)
        {
            // 覆盖当前区间，拿去处理
        }else
        {
            if (i.l <= mid)
            {
                vec[a * 2].push_back(i);
                cnt1 += (i.r >= r);
            }
            if (i.r > mid)
            {
                vec[a * 2 + 1].push_back(i);
                cnt2 += (i.l <= l);
            }
        }
    vector<node>().swap(vec[a]);
    if (cnt1 <= cnt2)
    {
        div(a * 2, l, mid);
        div(a * 2 + 1, mid + 1, r);
    }else
    {
        div(a * 2 + 1, mid + 1, r);
        div(a * 2, l, mid);
    }
    // 撤销
}

好的，现在来到证明环节了。
考虑若当前在节点 i，使用的总空间有多少。
我们可以把存储的修改分成两种，一种是覆盖整个区间的，另一种是不覆盖的。
不难发现任意时刻不覆盖整个区间的修改量是 O(n) 的，因为每个区间修改至多分裂出来一个前缀修改和一个后缀修改。
接下来考虑覆盖整个区间的。也就是说我们要统计，对于 i 的祖先链，先向 i 的方向递归的节点给另一个子节点留下的覆盖整个区间的修改个数。

考虑任意一个先向 i 递归的祖先节点 a，不妨设 i 在 a 的左子树，跨过 mid 的前缀有 x 个后缀有 y 个。
于是我们有 x \ge y，且这一步贡献的空间复杂度是 y
同时，对于所有的前缀，在递归进入 a 的左儿子之后就会被删除（因为覆盖了整个区间），且在回溯之前都不会再出现。
那我们不妨将这 y 份空间复杂度均摊到 x 个前缀上面。每个位置分到的复杂度是 O(1) 的。
由于总修改数量是 O(n) 的，所以任意时刻空间复杂度 O(n)

完结撒花！

貌似空间线性的线段树分治写法有好多种，比如先扔进左儿子，然后回溯的时候再把区间取回来的。
不过目前我所知道的写法里面这个应该算是最简单的了。
模板题，<20M