当「分块」与「线段树」同时「闪耀」—— 请输入文本

· · 休闲·娱乐

I.前置知识

在阅读本文前，作者希望你能够做到：

  1. 线段树的原理与代码；
  2. 分块的思维；
  3. 本文章中的 \log 一律指以 2 为底的对数。

    II.对于「线段树」与「分块」的优缺点分析

    • 线段树：查询复杂度优秀为 O(\log n)，但每次修改区间太过繁琐；

我们将它们的优点结合，采用「大区间采用分块」+「小区间线段树修改」达到了惊人的「O(12\log\sqrt n)」的单次询问，其中 12 为常数。

接下来，我们从分块的优化入手。

III.分散点的修改

我们将每一个块内建一个线段树，在查找分散点的修改的时候，我们可以直接用线段树区间修改： 此时对于分散的块，我们就可以实现 \log 的操作，由于修改长度为 \sqrt n，此时分散点的修改为 \log \sqrt n。

IV.整合块的修改

我们把一个块看成一个点，此时变成了一个长度为 \sqrt n 的序列，我们每次对于完整块的修改其实是在这个序列上区修，再建一颗线段树即可： 此时对于完整的块我们也可实现 \log 的操作。

至此，我们实现了 \log \sqrt n 的修改。

查询同理。

但是，我们发现，对于一个 [l,r]，这个方法的区间修改会进行 3 次：

也就是说，它的常数达到了 3\times 4 = 12！！！

V.对比

对比普通的线段树 O(4\log n) 的复杂度，我们发现（以下视为 n 与修改个数复杂度同阶）：

而且我们也可以证明在 n 取任意数 \frac{4\log n}{12 \log \sqrt n} \approx 0.667。

我们还有什么更好的优化吗？

此时的常数，成为了最大的问题，我们需要减少修改次数？

或者，再次从「分块」与「线段树」中下手？？？

VI.事情开始抽象起来

我们改变分块的大小 k，发现需要求 2\log k + \log \frac{n}{k} 的最小值。

2\log k + \log \frac{n}{k}\\ =\log k^2 + \log \frac{n}{k}\\ =\log (k^2\times \frac{n}{k})\\ =\log nk \end{array}

发现在块长取 1 时有最小值 \log n。

VII.代码（以 [P3372]() 为例）：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
#define int long long
struct ST {
    int l,r,mid;
    int sum,tag;
}a[N << 2];
int b[N];
int ls(int p) {
    return p << 1;
}
int rs(int p) {
    return p << 1 | 1;
}
void pushup(int p) {
    a[p].sum = a[ls(p)].sum + a[rs(p)].sum;
}
void build(int p,int l,int r) {
    a[p].l = l,a[p].r = r,a[p].mid = (l + r) / 2;
    if(l == r) {
        a[p].sum = b[l];
        return ;
    }
    build(ls(p),a[p].l,a[p].mid);
    build(rs(p),a[p].mid + 1,a[p].r);
    pushup(p);
}
void pushdown(int p) {
    if(!a[p].tag) return ;
    a[ls(p)].tag += a[p].tag;
    a[rs(p)].tag += a[p].tag;
    a[ls(p)].sum += (a[ls(p)].r - a[ls(p)].l + 1) * a[p].tag;
    a[rs(p)].sum += (a[rs(p)].r - a[rs(p)].l + 1) * a[p].tag;
    a[p].tag = 0;
    return ;
}
void update(int p,int l,int r,int k) {
    if(l <= a[p].l && a[p].r <= r) {
        a[p].sum += (a[p].r - a[p].l + 1) * k;
        a[p].tag += k;
        return ;
    }
    pushdown(p);
    if(l <= a[p].mid) update(ls(p),l,r,k);
    if(a[p].mid < r) update(rs(p),l,r,k);
    pushup(p);
}
int query(int p,int l,int r) {
    if(l <= a[p].l && a[p].r <= r) {
        return a[p].sum;
    }
    pushdown(p);
    int res = 0;
    if(l <= a[p].mid) res += query(ls(p),l,r);
    if(a[p].mid < r) res += query(rs(p),l,r);
    return res;
}
signed main() {
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> b[i];
    build(1,1,n);
    while(m--) {
        int op,l,r;
        cin >> op >> l >> r;
        if(op == 1) {
            int k;cin >> k;
            update(1,l,r,k);
        }
        else cout << query(1,l,r) << endl;
    }
}

VIII.后记

本文章其实是笔者对 基于多层分块嵌套的快速区间查询+修改算法 的一种理解，把它放在算法理论是因为讲了线段树时间复杂度最优的证明（算其中一种吧，可能有点不太严谨）如果实在不行就请哪位管理员高抬贵手放进休闲娱乐吧。