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

I.前置知识

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

线段树的原理与代码；
分块的思维；
本文章中的 $\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

次：

$[l,L_\text{block.l}]$
$[\text{block.l},\text{block.r}]$
$[R_\text{block.r},r]$

也就是说，它的常数达到了

3\times 4 = 12

！！！

V.对比

对比普通的线段树

O(4\log n)

的复杂度，我们发现（以下视为

n

与修改个数复杂度同阶）：

在 $n=10^5$ 时快了 $-\frac{1}{3}$ 倍；
在 $n=10^6$ 时快了 $-\frac{1}{3}$ 倍。

而且我们也可以证明在

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 为例）：

CPP

#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.后记

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

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

文章操作

I.前置知识

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

III.分散点的修改

IV.整合块的修改

V.对比

VI.事情开始抽象起来

VII.代码（以 P3372 为例）：

VIII.后记

相关推荐

评论

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