多层分块

· · 题解

简介

本篇题解以双层分块例，讲解了多层分块解决本题的方法。

双层分块

算法流程

将序列分块后，对散块暴力，剩下的问题又变回了单点修改、区间求和。于是可以将每个块看着整体，权值为块内数的和，再次进行分块。本篇题解提供一种简洁的写法。

首先取一个 B，满足 n<B^3，本题可以取 B=2^7。以 B 为一块，进行双层分块。

对于第一层，第 x 块包含原序列中 [xB,(x+1)B) 的位置。对于第二层，第 x 块包含第一层 [xB,(x+1)B) 中的块。

记 d(x)=\lfloor\frac{x}{B}\rfloor，表示 x 在第一层所在的块编号，同时也是第一层第 x 块在第二层所在的块编号。

用 a 表示原序列，记 p_i 为第一层第 i 块包含的数的和，q_i 为第二层第 i 块包含的块的 p_i 和。维护 A,B,C 三个序列：

考虑查询 [x,n] 的和。将 [x,n] 拆成三段：[x,(d(x)+1)B),[(d(x)+1)B,(d(d(x))+1)B^2),[(d(d(x))+1)B^2,n]。可以发现，A_x,B_{d(x)},C_{d(d(x))} 恰好为这三段，故答案为 A_x+B_{d(x)}+C_{d(d(x))}。

对于查询区间和，差分为两个后缀即可。

代码实现：

// d(x)=x/(2^7)=x>>7
// 求 [x,n] 的和
int ask(int x) { return s1[x] + s2[x >> 7] + s3[x >> 14]; }
// 求 [l,r] 的和
int ask(int l, int r) { return ask(l) - ask(r + 1); }

考虑加 a_x 加上 y。具体地：

代码实现：

void upd(int x, int y) {
    REP(i, x >> 7 << 7, x) s1[i] += y;
    REP(i, x >> 14 << 7, (x >> 7) - 1) s2[i] += y;
    REP(i, 0, (x >> 14) - 1) s3[i] += y;
}

考虑时间复杂度。查询复杂度显然为 \mathcal O(1)。对于修改，复杂度为 \mathcal O(B)，取 B=n^{1/3}，复杂度为 \mathcal O(n^{1/3})。

代码实现

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
using namespace std;
namespace Milkcat {
    typedef long long LL;
    typedef pair<LL, LL> pii;
    const int N = 5e5 + 5;
    namespace BLK {
        int s1[N], s2[N], s3[N];
        void upd(int x, int y) {
            REP(i, x >> 7 << 7, x) s1[i] += y;
            REP(i, x >> 14 << 7, (x >> 7) - 1) s2[i] += y;
            REP(i, 0, (x >> 14) - 1) s3[i] += y;
        }
        int ask(int x) { return s1[x] + s2[x >> 7] + s3[x >> 14]; }
        int ask(int l, int r) { return ask(l) - ask(r + 1); }
    }
    int n, q, o, x, y;
    int main() {
        cin >> n >> q;
        REP(i, 1, n) cin >> x, BLK::upd(i, x);
        REP(te, 1, q) {
            cin >> o >> x >> y;
            if (o == 1) BLK::upd(x, y);
            if (o == 2) cout << BLK::ask(x, y) << '\n';
        }
        return 0;
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int T = 1;
    while (T --) Milkcat::main();
    return 0;
}

多层分块

算法流程

对于 z 层分块，我们需要取合适的 B 使得 B^{z+1}>n。令 d^k(x)=d(d^{k-1}(x))，d^1(x)=d(x)。

维护 A_{z,i}=\sum_{j=(i+[z>1])B^{z-1}}^{(d(i)+1)B^z-1}a_j。

修改时，[x,n] 的答案为 \sum_{i=0}^{z}A_{\lfloor\frac{x}{B^i}\rfloor}。

查询时，对于 A_0,把 [d(x)B,x] 加上 y，对于 A_z\text{ }(z>0)，把 [d^z(x)B,d^{z-1}(x)) 加上 y 即可。

考虑复杂度，查询为 \mathcal O(z)，修改为 \mathcal O(n^{1/(z+1)}).

代码实现

这是本题三层分块的实现，取 B=2^5。

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
using namespace std;
namespace Milkcat {
    typedef long long LL;
    typedef pair<LL, LL> pii;
    const int N = 5e5 + 5;
    namespace BLK {
        int s1[N], s2[N], s3[N], s4[N];
        void upd(int x, int y) {
            REP(i, x >> 5 << 5, x) s1[i] += y;
            REP(i, x >> 10 << 5, (x >> 5) - 1) s2[i] += y;
            REP(i, x >> 15 << 5, (x >> 10) - 1) s3[i] += y;
            REP(i, 0, (x >> 15) - 1) s4[i] += y;
        }
        int ask(int x) { return s1[x] + s2[x >> 5] + s3[x >> 10] + s4[x >> 15]; }
        int ask(int l, int r) { return ask(l) - ask(r + 1); }
    }
    int n, q, o, x, y;
    int main() {
        cin >> n >> q;
        REP(i, 1, n) cin >> x, BLK::upd(i, x);
        REP(te, 1, q) {
            cin >> o >> x >> y;
            if (o == 1) BLK::upd(x, y);
            if (o == 2) cout << BLK::ask(x, y) << '\n';
        }
        return 0;
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int T = 1;
    while (T --) Milkcat::main();
    return 0;
}