算法学习笔记 -- 数列分块

算法学习笔记 -- 数列分块

Coast23
  2025-09-16 23:09:57 2025-09-16 23:09:57 创建   2025-09-16 23:39:39 2025-09-16 23:39:39 更新    7.5k 字  42 分钟  

数列分块基本思想

分块的基本思想就是, 把区间划分为若干连续的大块, 把区间操作按照大块和小块(散块)作不同处理, 从而取得比直接暴力更优的复杂度.

比如, 有两种操作, 区间加法(对区间的每个数都加) 与区间和 (求区间的每个数的和)

如果是朴素的暴力 (遍历加, 遍历求和), 那么单次操作复杂度是的.

如果我们提前把区间划分为若干长度为的块 (), 并维护这些大块的区间和与区间加法标记, 对大块的单次区间操作都可以做到. 对于每次修改或查询操作, 操作区间可以分成若干大块和至多个小块. 大块的数量不会超过, 小块的长度不会超过, 于是单次区间操作的时间复杂度就可以做到, 由均值不等式, 取, 我们就可以把单次区间操作做到, 而且常数极小.

思想很简单, 实现也不困难.

数列分块代码框架

分块的基本代码框架如下:

#include <cmath>
#include <cstdio>
#include <vector>
#include <cctype>
#define ll long long

ll read(){
    ll x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

ll min(ll a, ll b){return a < b ? a : b;}

void solve(){
    int n = read();                 // 区间长度
    int B = sqrt(n);                // 大块长度
    int N = (n - 1) / B + 1;        // 大块个数
    std::vector<ll> a(n+1);         // 序列值
    std::vector<int> id(n+1);       // id[x]: 第x个数属于第几个大块
    std::vector<int> L(N+1), R(N+1);// 第k个大块的区间左右边界
    for(int i = 1; i <= n; ++i){
        a[i] = read();              // 读入初始序列
        id[i] = (i - 1) / B + 1;    // 给每个大块编号, 自行推导为什么是 (i-1)/B+1
    }
    for(int i = 1; i <= N; ++i){    // 给每个大块设置边界
        L[i] = (i - 1) * B + 1;
        R[i] = min(i * B, n);       // 最后一个块的右边界不能超过n
    }

    auto modify = [&](int l, int r, ll c) -> void {
        if(id[l] == id[r]){ // 在同一个大块中, 直接暴力修改
            for(int i = l; i <= r; ++i) /*对a[i]暴力修改*/
            return;
        }
        // 否则, 就拆分成左散块+右散块+中间大块
        // 左散块的区间是 [l, R[id[l]]], 右散块的范围是 [L[id[r]], r]
        // 中间大块的编号范围是 (id[l], id[r])
        
        // 对左右散块操作
        for(int i = l; i <= R[id[l]]; ++i) /*对a[i]暴力修改*/
        for(int i = L[id[r]]; i <= r; ++i) /*对a[i]暴力修改*/
        
        // 对大块操作
        for(int i = id[l]+1; i < id[r]; ++i) /*对第i个大块做修改*/
        return;
    };

    auto query = [&](int l, int r) -> ll {
        ll ans = 0; // 分类方式同modify
        if(id[l] == id[r]){
            for(int i = l; i <= r; ++i) /*对下标暴力统计*/
            return ans;
        }
        for(int i = l; i <= R[id[l]]; ++i)    /*对下标暴力统计*/
        for(int i = L[id[r]]; i <= r; ++i)    /*对下标暴力统计*/
        for(int i = id[l]+1; i < id[r]; ++i)  /*统计各个大块*/
        return ans;
    };

    int q = read();
    while(q--){
        // 假定 op = 0: 修改区间 [l, r]; op = 1: 查询区间 [l, r]
        int op = read(), l = read(), r = read();
        if(!op) modify(l, r, read());
        else printf("%lld\n", query(l, r));
    }
}

int main(){
    solve();
}

入门题集

以下是比较裸的入门题.

1. 数列分块入门 1 [区间加法, 单点查询]

AC Code
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#define ll long long

ll read(){
    ll x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

ll min(ll a, ll b){return a < b ? a : b;}

void solve(){
    int n = read();
    int B = sqrt(n);
    int N = (n - 1) / B + 1;
    std::vector<ll> a(n+1);
    std::vector<int> id(n+1);
    std::vector<int> L(N+1), R(N+1);
    std::vector<ll> tag(N+1); // 区间加法标记
    for(int i = 1; i <= n; ++i){
        a[i] = read();
        id[i] = (i - 1) / B + 1;
    }
    for(int i = 1; i <= N; ++i){
        L[i] = (i - 1) * B + 1;
        R[i] = min(i * B, n);
    }
    
    auto modify = [&](int l, int r, ll c) -> void {
        if(id[l] == id[r]){
            for(int i = l; i <= r; ++i) a[i] += c;
            return;
        }
        for(int i = l; i <= R[id[l]]; ++i) a[i] += c;
        for(int i = L[id[r]]; i <= r; ++i) a[i] += c;
        for(int i = id[l]+1; i < id[r]; ++i) tag[i] += c;
    };

    auto query = [&](int x) -> ll {
        return a[x] + tag[id[x]];
    };

    for(int i = 1; i <= n; ++i){
        int op = read(), l = read(), r = read();
        ll c = read();
        if(!op) modify(l, r, c);
        else printf("%lld\n", query(r));
    }
}

int main(){
    solve();
}

2. 数列分块入门 4 [区间加法, 区间求和]

AC Code
#include <map>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#define ll long long
#define inf 0x3f3f3f3f

ll read(){
    ll x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return f ? x : -x;
}

ll min(ll a, ll b){return a < b? a : b;}
ll max(ll a, ll b){return a > b? a : b;}
ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;}

void solve(){
    int n = read();
    int B = sqrt(n);
    int N = (n - 1) / B + 1;
    std::vector<ll> a(n+1);
    std::vector<int> id(n+1);
    std::vector<int> L(N+1), R(N+1);
    std::vector<ll> tag(N+1), sum(N+1);
    for(int i = 1; i <= n; ++i){
        a[i] = read();
        id[i] = (i-1) / B + 1;
        sum[id[i]] += a[i];
    }
    for(int i = 1; i <= N; ++i){
        L[i] = (i-1) * B + 1;
        R[i] = min(i * B, n);
    }
    
    auto modify = [&](int l, int r, ll c) -> void {
        if(id[l] == id[r]){
            for(int i = l; i <= r; ++i) a[i] += c, sum[id[i]] += c;
            return;
        }
        for(int i = l; i <= R[id[l]]; ++i) a[i] += c, sum[id[i]] += c;
        for(int i = L[id[r]]; i <= r; ++i) a[i] += c, sum[id[i]] += c;
        for(int i = id[l] + 1; i < id[r]; ++i) tag[i] += c, sum[i] += c * (R[i] - L[i] + 1);
    };

    auto query = [&](int l, int r, ll c) -> ll {
        ll res = 0;
        if(id[l] == id[r]){
            for(int i = l; i <= r; ++i) res += a[i] + tag[id[i]];
            return (res + 1145141919LL * (c+1)) % (c+1);
        }
        for(int i = l; i <= R[id[l]]; ++i) res += a[i] + tag[id[i]];
        for(int i = L[id[r]]; i <= r; ++i) res += a[i] + tag[id[i]];
        for(int i = id[l] + 1; i < id[r]; ++i) res += sum[i];
        return (res + 1145141919LL * (c+1)) % (c+1);
    };

    for(int i = 1; i <= n; ++i){
        int opt = read(), l = read(), r = read(); ll c = read();
        if(!opt) modify(l, r, c);
        else printf("%lld\n", query(l, r, c));
    }
}

int main(){
//    freopen("input.txt", "r", stdin);
    int t = 1;
    while(t--) solve();
}

3. 数列分块入门7 [区间加法, 区间乘法, 区间求和]

Hint

这题需要注意的就是加法标记和乘法标记的优先级, 以及在暴力修改散块前, 需要先下放标记.

AC Code
#include <map>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <ext/rope>
#define ll long long
#define mod 10007

ll read(){
    ll x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return f ? x : -x;
}

ll min(ll a, ll b){return a < b? a : b;}
ll max(ll a, ll b){return a > b? a : b;}
ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;}

void solve(){
    int n = read();
    int B = sqrt(n);
    int N = (n - 1) / B + 1;
    std::vector<ll> a(n+1);
    std::vector<int> id(n+1);
    std::vector<int> L(N+1), R(N+1);
    std::vector<ll> add(N+1), mul(N+1, 1);
    for(int i = 1; i <= N; ++i){
        L[i] = (i - 1) * B + 1;
        R[i] = min(i * B, n);
    }
    for(int i = 1; i <= n; ++i){
        a[i] = read();
        id[i] = (i - 1) / B + 1;
    }

    auto Pushdown = [&](int x) -> void {
        for(int i = L[x]; i <= R[x]; ++i){
            a[i] = (a[i] * mul[id[i]]) % mod + add[id[i]];
            a[i] %= mod;
        }
        mul[x] = 1; add[x] = 0;
    };

    auto Add = [&](int l, int r, ll c) -> void {
        if(id[l] == id[r]){
            Pushdown(id[l]);
            for(int i = l; i <= r; ++i) a[i] += c, a[i] %= mod;
            return;
        }
        Pushdown(id[l]); Pushdown(id[r]);
        for(int i = l; i <= R[id[l]]; ++i) a[i] += c, a[i] %= mod;
        for(int i = id[l] + 1; i < id[r]; ++i) add[i] += c, add[i] %= mod;
        for(int i = L[id[r]]; i <= r; ++i) a[i] += c, a[i] %= mod;
    };

    auto Mul = [&](int l, int r, ll c) -> void {
        if(id[l] == id[r]){
            Pushdown(id[l]);
            for(int i = l; i <= r; ++i) a[i] *= c, a[i] %= mod;
            return;
        }
        Pushdown(id[l]); Pushdown(id[r]);
        for(int i = l; i <= R[id[l]]; ++i) a[i] *= c, a[i] %= mod;
        for(int i = id[l] + 1; i < id[r]; ++i) mul[i] *= c, add[i] *= c, mul[i] %= mod, add[i] %= mod;
        for(int i = L[id[r]]; i <= r; ++i) a[i] *= c, a[i] %= mod;
    };

    auto query = [&](int x) -> ll {
        ll res = ((a[x] * mul[id[x]]) % mod + add[id[x]]) % mod;
        return (res + mod) % mod;
    };

    for(int i = 1; i <= n; ++i){
        int opt = read(), l = read(), r = read(); ll c = read();
        if(opt == 0) Add(l, r, c);
        else if(opt == 1) Mul(l, r, c);
        else printf("%lld\n", query(r));
    //    for(int i = 1; i <= n; ++i) printf("%lld ", a[i]); puts("");
    }
}

int main(){
//    freopen("input.txt", "r", stdin);
    int t = 1;
    while(t--) solve();
}

4. 数列分块入门8 [区间赋值, 值查询]

Hint

用一个赋值标记维护大块的值, 如果是散块或者未标记的大块, 就暴力查询.

AC Code
#include <map>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#define ll long long
#define inf 1e18

ll read(){
    ll x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return f ? x : -x;
}

ll min(ll a, ll b){return a < b? a : b;}
ll max(ll a, ll b){return a > b? a : b;}
ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;}

void solve(){
    int n = read();
    int B = sqrt(n);
    int N = (n - 1) / B + 1;
    std::vector<ll> a(n+2);
    std::vector<int> id(n+1);
    std::vector<int> L(N+1), R(N+1);
    std::vector<ll> tag(N+1, 1e18);
    for(int i = 1; i <= n; ++i){
        a[i] = read();
        id[i] = (i - 1) / B + 1;
    }
    for(int i = 1; i <= N; ++i){
        L[i] = (i - 1) * B + 1;
        R[i] = min(i * B, n);
    }

    auto pushdown = [&](int x) -> void {
        if(tag[x] == inf) return;
        for(int i = L[x]; i <= R[x]; ++i) a[i] = tag[x];
        tag[x] = inf;
    };

    auto op = [&](int l, int r, int c) -> int {
        int res = 0;
        if(id[l] == id[r]){
            pushdown(id[l]);
            for(int i = l; i <= r; ++i){
                if(a[i] == c) ++res;
                a[i] = c;
            }
            return res;
        }
        pushdown(id[l]); pushdown(id[r]);
        for(int i = l; i <= R[id[l]]; ++i){
            if(a[i] == c) ++res;
            a[i] = c;
        }
        for(int i = L[id[r]]; i <= r; ++i){
            if(a[i] == c) ++res;
            a[i] = c;
        }
        for(int i = id[l]+1; i < id[r]; ++i){
            if(tag[i] != inf){
                if(tag[i] == c) res += R[i] - L[i] + 1;
                tag[i] = c;
            }
            else{
                for(int j = L[i]; j <= R[i]; ++j){
                    if(a[j] == c) ++res;
                }
                tag[i] = c;
            }
        }
        return res;
    };
    for(int i = 1; i <= n; ++i){
        int l = read(), r = read(), c = read();
        printf("%d\n", op(l, r, c));
    }
}

int main(){
//    freopen("input.txt", "r", stdin);
    int t = 1;
    while(t--) solve();
}

5. 数列分块入门5 [区间开方, 区间求和]

Hint

假设, 开方相当于指数除以, 即. 当指数变成的时候, 也就是, 此时对的开方操作不再有意义. 也就是说, 开方的次数上界是.

因此, 我们只需要维护大块的区间最大值, 每次只暴力做有意义的开方即可. 时间复杂度大概是.

AC Code
#include <map>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#define ll long long
#define inf 0x3f3f3f3f

ll read(){
    ll x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return f ? x : -x;
}

ll min(ll a, ll b){return a < b? a : b;}
ll max(ll a, ll b){return a > b? a : b;}
ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;}

void solve(){
    int n = read();
    int B = sqrt(n);
    int N = (n - 1) / B + 1;
    std::vector<ll> a(n+1);
    std::vector<int> id(n+1);
    std::vector<int> L(N+1), R(N+1);
    std::vector<ll> sum(N+1), maxx(N+1, -1e18); 
    for(int i = 1; i <= N; ++i){
        L[i] = (i - 1) * B + 1;
        R[i] = min(i * B, n);
    }
    for(int i = 1; i <= n; ++i){
        a[i] = read();
        id[i] = (i - 1) / B + 1;
        sum[id[i]] += a[i];
        if(a[i]) maxx[id[i]] = max(maxx[id[i]], a[i]);
    }

    auto modify = [&](int l, int r) -> void {
        if(id[l] == id[r]){
            if(maxx[id[l]] <= 1) return;
            for(int i = l; i <= r; ++i){
                sum[id[i]] -= a[i];
                a[i] = sqrt(a[i]);
                sum[id[i]] += a[i];
            }
            return;
        }
        // 左
        if(maxx[id[l]] > 1){
            for(int i = l; i <= R[id[l]]; ++i){
                sum[id[i]] -= a[i];
                a[i] = sqrt(a[i]);
                sum[id[i]] += a[i];
            }
        }
        for(int i = id[l] + 1; i < id[r]; ++i){
            if(maxx[i] <= 1) continue;
            maxx[i] = -1e18;
            for(int j = L[i]; j <= R[i]; ++j){
                sum[i] -= a[j];
                a[j] = sqrt(a[j]);
                sum[i] += a[j];
                maxx[i] = max(maxx[i], a[j]);
            }
        }
        // 右
        if(maxx[id[r]] > 1){
            for(int i = L[id[r]]; i <= r; ++i){
                sum[id[i]] -= a[i];
                a[i] = sqrt(a[i]);
                sum[id[i]] += a[i];
            }
        }
    };

    auto query = [&](int l, int r) -> ll {
        ll res = 0;
        if(id[l] == id[r]){
            for(int i = l; i <= r; ++i) res += a[i];
            return res;
        }
        for(int i = l; i <= R[id[l]]; ++i) res += a[i];
        for(int i = id[l] + 1; i < id[r]; ++i) res += sum[i];
        for(int i = L[id[r]]; i <= r; ++i) res += a[i];
        return res;
    };

    for(int i = 1; i <= n; ++i){
        int opt = read(), l = read(), r = read();
        if(!opt) modify(l, r);
        else printf("%lld\n", query(l, r));
    }
}

int main(){
//    freopen("input.txt", "r", stdin);
    int t = 1;
    while(t--) solve();
}

6. 数列分块入门2 [区间加法, 小于的元素个数]

Hint

这题和前面的题略有不同, 为了快速求出小于的元素数, 我们会希望区间是有序的, 这样就可以通过二分快速求出答案. 因此, 除了维护原始序列外, 我们还要维护一个分块有序的序列. 对大块的区间加法不会改变, 但修改散块时, 我们在暴力加结束后, 还需要更新, 即对散块所在的大块重新排序. 显然, 单次修改和查询操作的复杂度都为.

AC Code
#include <map>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#define ll long long
#define inf 0x3f3f3f3f

ll read(){
    ll x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return f ? x : -x;
}

ll min(ll a, ll b){return a < b? a : b;}
ll max(ll a, ll b){return a > b? a : b;}
ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;}

void solve(){
    int n = read();
    int B = sqrt(n);
    int N = (n - 1) / B + 1;
    std::vector<ll> a(n+1), id(n+1), sorted(n+1);
    std::vector<ll> L(N+1), R(N+1), tag(N+1);

    for(int i = 1; i <= n; ++i){
        a[i] = read();
        sorted[i] = a[i];
        id[i] = (i - 1) / B + 1;
    }

    for(int i = 1; i <= N; ++i){
        L[i] = (i - 1) * B + 1;
        R[i] = min(i * B, n);
        std::sort(&sorted[L[i]], &sorted[R[i]+1]);
    }

    auto resort = [&](int id) -> void {
        for(int i = L[id]; i <= R[id]; ++i) sorted[i] = a[i];
        std::sort(&sorted[L[id]], &sorted[R[id]+1]);
    };

    auto modify = [&](int l, int r, ll c) -> void {
        if(id[l] == id[r]){
            for(int i = l; i <= r; ++i) a[i] += c;
            resort(id[l]);
            return;
        }
        // 左
        for(int i = l; i <= R[id[l]]; ++i) a[i] += c;
        resort(id[l]);
        // 中
        for(int i = id[l] + 1; i < id[r]; ++i) tag[i] += c;
        // 右
        for(int i = L[id[r]]; i <= r; ++i) a[i] += c;
        resort(id[r]);
    };

    auto query = [&](int l, int r, ll x) -> int {
        int res = 0;
        if(id[l] == id[r]){
            for(int i = l; i <= r; ++i){
                if(a[i] + tag[id[i]] < x) ++res;
            }
            return res;
        }
        // 左
        for(int i = l; i <= R[id[l]]; ++i){
            if(a[i] + tag[id[i]] < x) ++res;
        }
        // 右
        for(int i = L[id[r]]; i <= r; ++i){
            if(a[i] + tag[id[i]] < x) ++res;
        }
        // 中: 二分
        for(int i = id[l] + 1; i < id[r]; ++i){
            ll target = x - tag[i];
            res += std::lower_bound(sorted.begin() + L[i], sorted.begin() + R[i] + 1, target) - (sorted.begin() + L[i]);
        }
        return res;
    };

    for(int i = 1; i <= n; ++i){
        int opt = read(), l = read(), r = read();
        ll c = read();
        if(!opt) modify(l, r, c);
        else printf("%d\n", query(l, r, c * c));
    } 
}

int main(){
//    freopen("input.txt", "r", stdin);
    int t = 1;
    while(t--) solve();
}

7. 教主的魔法 [区间加法, 大于等于的个数]

Hint

和上一题没有本质不同.

AC Code
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#define ll long long

ll read(){
    ll x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

ll min(ll a, ll b){return a < b ? a : b;}

void solve(){
    int n = read(), q = read();
    int B = sqrt(n);
    int N = (n - 1) / B + 1;
    std::vector<ll> a(n+2), sorted(n+2);
    std::vector<int> id(n+1);
    std::vector<int> L(N+1), R(N+1);
    std::vector<ll> tag(N+2, 0);
    for(int i = 1; i <= n; ++i){
        sorted[i] = a[i] = read();
        id[i] = (i - 1) / B + 1;
    }
    for(int i = 1; i <= N; ++i){
        L[i] = (i - 1) * B + 1;
        R[i] = min(i * B, n);
        std::sort(&sorted[L[i]], &sorted[R[i]+1]);
    }

    auto resort = [&](int x) -> void {
        for(int i = L[x]; i <= R[x]; ++i){
            a[i] += tag[x];
            sorted[i] = a[i];
        }
        std::sort(&sorted[L[x]], &sorted[R[x]+1]);
        tag[x] = 0;
    };

    auto modify = [&](int l, int r, ll c) -> void {
        if(id[l] == id[r]){
            for(int i = l; i <= r; ++i) a[i] += c;
            resort(id[l]); return;
        }
        for(int i = l; i <= R[id[l]]; ++i) a[i] += c;
        for(int i = L[id[r]]; i <= r; ++i) a[i] += c;
        resort(id[l]); resort(id[r]);
        for(int i = id[l] + 1; i < id[r]; ++i) tag[i] += c;
    };

    auto query = [&](int l, int r, ll c) -> int {
        int ans = 0;
        if(id[l] == id[r]){
            for(int i = l; i <= r; ++i) if(a[i] + tag[id[l]] >= c) ++ans;
            return ans;
        }
        for(int i = l; i <= R[id[l]]; ++i) if(a[i] + tag[id[i]] >= c) ++ans;
        for(int i = L[id[r]]; i <= r; ++i) if(a[i] + tag[id[i]] >= c) ++ans;
        for(int i = id[l] + 1; i < id[r]; ++i){
            auto it = std::lower_bound(&sorted[L[i]], &sorted[R[i]+1], c - tag[i]);
            if(it == &sorted[R[i]+1]) continue;
            ans += &sorted[R[i]+1] - it;
        }
        return ans;
    };

    while(q--){
        char op = ' '; while(op != 'A' and op != 'M') op = getchar();
        if(op == 'M'){
            int l = read(), r = read(); ll w = read();
            modify(l, r, w);
        }
        else if(op == 'A'){
            int l = read(), r = read(); ll c = read();
            printf("%d\n", query(l, r, c));
        }
    }
}

int main(){
    solve();
}

8. 数列分块入门3 [区间加法, 查询前驱]

Hint

这题和前两题几乎一样, 都是要维护一个大块的加法标记和有序序列.

AC Code
#include <map>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#define ll long long
#define inf 0x3f3f3f3f

ll read(){
    ll x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return f ? x : -x;
}

ll min(ll a, ll b){return a < b? a : b;}
ll max(ll a, ll b){return a > b? a : b;}
ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;}

void solve(){
    int n = read();
    int B = sqrt(n);
    int N = (n - 1) / B + 1;
    std::vector<ll> a(n+1), sorted(n+1);
    std::vector<int> id(n+1);
    std::vector<int> L(N+1), R(N+1);
    std::vector<ll> tag(N+1);
    for(int i = 1; i <= n; ++i){
        a[i] = read();
        sorted[i] = a[i];
        id[i] = (i - 1) / B + 1;
    }
    for(int i = 1; i <= N; ++i){
        L[i] = (i - 1) * B + 1;
        R[i] = min(i * B, n);
        std::sort(&sorted[L[i]], &sorted[R[i]+1]);
    }

    auto resort = [&](int id) -> void {
        for(int i = L[id]; i <= R[id]; ++i) sorted[i] = a[i];
        std::sort(&sorted[L[id]], &sorted[R[id]+1]);
    };

    auto modify = [&](int l, int r, ll c) -> void {
        if(id[l] == id[r]){
            for(int i = l; i <= r; ++i) a[i] += c;
            resort(id[l]); return;
        }
        for(int i = l; i <= R[id[l]]; ++i) a[i] += c;
        resort(id[l]);
        for(int i = L[id[r]]; i <= r; ++i) a[i] += c;
        resort(id[r]);
        for(int i = id[l] + 1; i < id[r]; ++i) tag[i] += c;
    };

    auto query = [&](int l, int r, ll x) -> ll {
        // 查询 x 前驱
        ll res = -1145141919810LL;
        if(id[l] == id[r]){
            for(int i = l; i <= r; ++i){
                if(a[i] + tag[id[i]] < x) res = max(res, a[i] + tag[id[i]]);
            }
            return res == -1145141919810LL ? -1 : res;
        }
        for(int i = l; i <= R[id[l]]; ++i){
            if(a[i] + tag[id[i]] < x) res = max(res, a[i] + tag[id[i]]);
        }
        for(int i = L[id[r]]; i <= r; ++i){
            if(a[i] + tag[id[i]] < x) res = max(res, a[i] + tag[id[i]]);
        }
        for(int i = id[l] + 1; i < id[r]; ++i){
            int pos = std::lower_bound(&sorted[L[i]], &sorted[R[i]+1], x - tag[i]) - &sorted[L[i]];
            if(pos > 0) res = max(res, sorted[L[i] + pos-1] + tag[i]);
        }
        return res == -1145141919810LL ? -1 : res;
    };

    for(int i = 0; i < n; ++i){
        int opt = read(), l = read(), r = read(); ll c = read();
        if(!opt) modify(l, r, c);
        else printf("%lld\n", query(l, r, c));
    }
}

int main(){
//    freopen("input.txt", "r", stdin);
    int t = 1;
    while(t--) solve();
}

9. 数列分块入门9 [无修改, 查询区间最小众数]

Hint

这题应该是莫队板子, 但我还不会莫队, 依旧使用分块的在线做法.

首先, 对于众数, 我们并不关心具体数值, 只关心每个数的出现次数, 因此我们可以先做一个离散化, 把序列映射到, 再考虑如何维护每个区间的众数.

注意到题目的内存限制给到了GB, 我们可以预处理出第个大块到第个大块的众数 (记为), 并预处理出前个大块中数字的频数作为辅助 (记为).

接下来考虑如何查询区间最小众数.

对于小区间 (区间在某个大块上), 我们直接暴力统计就行, 无伤大雅.

对于大区间, 显然, 整个大区间的众数, 只可能是某个大块的众数, 或者两个散块中的某个数.

全部大块的编号范围是 [id[l]+1, id[r]-1], 利用前面的预处理结果, 我们马上能得到全部大块的众数, 以及这个数(记作)在大块中的频数.

然后, 再加上在两个散块的频数, 就得到了在整个查询区间的频数.

然后, 再考虑散块中的数的频数, 和前面的比较、更新.

我的实现可能不太优雅, 仅供参考.

AC Code
#include <map>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#define ll long long
#define inf 1e18

ll read(){
    ll x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return f ? x : -x;
}

ll min(ll a, ll b){return a < b? a : b;}
ll max(ll a, ll b){return a > b? a : b;}
ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;}

void solve(){
    int n = read();
    std::vector<int> a(n+2);
    std::vector<int> vec; vec.reserve(n);
    for(int i = 1; i <= n; ++i) a[i] = read(), vec.push_back(a[i]);
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    int _n = vec.size();
    for(int i = 1; i <= n; ++i) a[i] = std::lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
    
    int B = sqrt(n);
    int N = (n - 1) / B + 1;
    std::vector<int> id(n+1);
    std::vector<int> L(N+1), R(N+1);
    for(int i = 1; i <= N; ++i){
        L[i] = (i - 1) * B + 1;
        R[i] = min(i * B, n);
    }
    for(int i = 1; i <= n; ++i) id[i] = (i - 1) / B + 1;

    std::vector<std::vector<int>> pos(_n);
    for(int i = 1; i <= n; ++i) pos[a[i]].push_back(i);
    std::vector<std::vector<int>> f(N+1, std::vector<int>(N+1, 0));
    // f[i][j]: 第 i 块到第 j 块的众数
    std::vector<int> cnt(_n+1);
    for(int i = 1; i <= N; ++i){
        int best = 0, freq = 0;
        if(i > 1) best = f[i-1][i-1];
        for(int j = i; j <= N; ++j){
            for(int k = L[j]; k <= R[j]; ++k){
                ++cnt[a[k]];
                if(cnt[a[k]] > freq or cnt[a[k]] == freq and vec[a[k]] < vec[best]){
                    freq = cnt[a[k]];
                    best = a[k];
                }
            }
            f[i][j] = best;
        }
        for(int j = i; j <= N; ++j) for(int k = L[j]; k <= R[j]; ++k) cnt[a[k]] = 0;
    }

    // s[i][v] : 前 i 个块中, 值为 v 的元素个数
    std::vector<std::vector<int>> s(N+1, std::vector<int>(_n, 0));
    for(int i = 1; i <= N; ++i){
        for(int j = 0; j < _n; ++j){
            s[i][j] = s[i-1][j];
        }
        for(int k = L[i]; k <= R[i]; ++k) ++s[i][a[k]];
    }

    std::vector<int> c(_n+1);

    auto query = [&](int l, int r) -> int {
        if(id[l] == id[r]){
            int freq = 0, best = a[l];
            for(int i = l; i <= r; ++i){
                ++c[a[i]];
                if(c[a[i]] > freq or c[a[i]] == freq and vec[a[i]] < vec[best]){
                    freq = c[a[i]];
                    best = a[i];
                }
            }
            for(int i = l; i <= r; ++i) c[a[i]] = 0;
            return best;
        }
        // 随便初始值
        int ans = 0, freq = 0;
        // 中间
        if(id[l] + 1 <= id[r] - 1){
            ans = f[id[l]+1][id[r]-1];
            freq = s[id[r]-1][ans] - s[id[l]][ans];
        }
        for(int i = l; i <= R[id[l]]; ++i) ++c[a[i]];
        for(int i = L[id[r]]; i <= r; ++i) ++c[a[i]];
        freq += c[ans]; // 加上散块频数

        for(int i = l; i <= R[id[l]]; ++i){
            int cur_freq = c[a[i]] + s[id[r]-1][a[i]] - s[id[l]][a[i]];
            if(cur_freq > freq or cur_freq == freq and vec[a[i]] < vec[ans]){
                ans = a[i];
                freq = cur_freq;
            }
        }
        for(int i = L[id[r]]; i <= r; ++i){
            int cur_freq = c[a[i]] + s[id[r]-1][a[i]] - s[id[l]][a[i]];
            if(cur_freq > freq or cur_freq == freq and vec[a[i]] < vec[ans]){
                ans = a[i];
                freq = cur_freq;
            }
        }
        for(int i = l; i <= R[id[l]]; ++i) c[a[i]] = 0;
        for(int i = L[id[r]]; i <= r; ++i) c[a[i]] = 0;
        return ans;
    };

    for(int i = 1; i <= n; ++i){
        int l = read(), r = read();
        printf("%d\n", vec[query(l, r)]);
    }
}

int main(){
 //   freopen("in.txt", "r", stdin);
    int t = 1;
    while(t--) solve();
}

10. [Violet] 蒲公英 [无修区间众数, 强制在线]

Hint

双倍经验.

AC Code
#include <map>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#define ll long long
#define inf 1e18

ll read(){
    ll x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return f ? x : -x;
}

ll min(ll a, ll b){return a < b? a : b;}
ll max(ll a, ll b){return a > b? a : b;}
ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;}

void solve(){
    int n = read(), m = read();
    std::vector<int> a(n+2);
    std::vector<int> vec; vec.reserve(n);
    for(int i = 1; i <= n; ++i) a[i] = read(), vec.push_back(a[i]);
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    int _n = vec.size();
    for(int i = 1; i <= n; ++i) a[i] = std::lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
    
    int B = sqrt(n);
    int N = (n - 1) / B + 1;
    std::vector<int> id(n+1);
    std::vector<int> L(N+1), R(N+1);
    for(int i = 1; i <= N; ++i){
        L[i] = (i - 1) * B + 1;
        R[i] = min(i * B, n);
    }
    for(int i = 1; i <= n; ++i) id[i] = (i - 1) / B + 1;

    std::vector<std::vector<int>> pos(_n);
    for(int i = 1; i <= n; ++i) pos[a[i]].push_back(i);
    std::vector<std::vector<int>> f(N+1, std::vector<int>(N+1, 0));
    // f[i][j]: 第 i 块到第 j 块的众数
    std::vector<int> cnt(_n+1);
    for(int i = 1; i <= N; ++i){
        int best = 0, freq = 0;
        if(i > 1) best = f[i-1][i-1]; // 小优化, 可有可无
        for(int j = i; j <= N; ++j){
            for(int k = L[j]; k <= R[j]; ++k){
                ++cnt[a[k]];
                if(cnt[a[k]] > freq or cnt[a[k]] == freq and vec[a[k]] < vec[best]){
                    freq = cnt[a[k]];
                    best = a[k];
                }
            }
            f[i][j] = best;
        }
        for(int j = i; j <= N; ++j) for(int k = L[j]; k <= R[j]; ++k) cnt[a[k]] = 0;
    }

    // s[i][v] : 前 i 个块中, 值为 v 的元素个数
    std::vector<std::vector<int>> s(N+1, std::vector<int>(_n, 0));
    for(int i = 1; i <= N; ++i){
        for(int j = 0; j < _n; ++j){
            s[i][j] = s[i-1][j];
        }
        for(int k = L[i]; k <= R[i]; ++k) ++s[i][a[k]];
    }
    
    auto count = [&](int l, int r, int v) -> int {
        auto L = std::lower_bound(pos[v].begin(), pos[v].end(), l);
        auto R = std::upper_bound(pos[v].begin(), pos[v].end(), r);
        return std::distance(L, R);
    };

    std::vector<int> c(_n+1);

    auto query = [&](int l, int r) -> int {
        if(id[l] == id[r]){
            int freq = 0, best = a[l];
            for(int i = l; i <= r; ++i){
                ++c[a[i]];
                if(c[a[i]] > freq or c[a[i]] == freq and vec[a[i]] < vec[best]){
                    freq = c[a[i]];
                    best = a[i];
                }
            }
            for(int i = l; i <= r; ++i) c[a[i]] = 0;
            return best;
        }
        int ans = 0, freq = 0;
        // 中间
        if(id[l] + 1 <= id[r] - 1){
            ans = f[id[l]+1][id[r]-1];
            freq = s[id[r]-1][ans] - s[id[l]][ans];
        }

        for(int i = l; i <= R[id[l]]; ++i) ++c[a[i]];
        for(int i = L[id[r]]; i <= r; ++i) ++c[a[i]];
        freq += c[ans]; // 加上散块频数

        for(int i = l; i <= R[id[l]]; ++i){
            int cur_freq = c[a[i]] + s[id[r]-1][a[i]] - s[id[l]][a[i]];
            if(cur_freq > freq or cur_freq == freq and vec[a[i]] < vec[ans]){
                ans = a[i];
                freq = cur_freq;
            }
        }
        for(int i = L[id[r]]; i <= r; ++i){
            int cur_freq = c[a[i]] + s[id[r]-1][a[i]] - s[id[l]][a[i]];
            if(cur_freq > freq or cur_freq == freq and vec[a[i]] < vec[ans]){
                ans = a[i];
                freq = cur_freq;
            }
        }
        for(int i = l; i <= R[id[l]]; ++i) c[a[i]] = 0;
        for(int i = L[id[r]]; i <= r; ++i) c[a[i]] = 0;
        return ans;
    };

    int last = 0;

    for(int i = 1; i <= m; ++i){
        int l = read(), r = read();
        l = (l + last - 1) % n + 1;
        r = (r + last - 1) % n + 1;
        if(l > r) std::swap(l, r);
        last = vec[query(l, r)];
        printf("%d\n", last);
    }
}

int main(){
 //   freopen("in.txt", "r", stdin);
    int t = 1;
    while(t--) solve();
}

11. ycz的妹子

Hint

题意理解有一定难度.

初始建块的时候, 要注意要取.

用一个数组 has 维护第个城市有没有人, 用一个数组 cnt 维护第个大块的人数.

查找第个人所在的大块, 可以直接暴力遍历 cnt$ 查, 没必要再维护 cnt 前缀和之类的.

其它没啥好说的, 看代码就行.

AC Code
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#define ll long long

ll read(){
    ll x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

ll min(ll a, ll b){return a < b ? a : b;}

void solve(){
    int n = 500000;
    int B = sqrt(n);
    int N = (n - 1) / B + 1;
    int k = read(), m = read();
    std::vector<ll> a(n+1);
    std::vector<bool> has(n+1);
    std::vector<int> id(n+1);
    std::vector<int> L(N+1), R(N+1), cnt(N+1);
    ll sum = 0;
    for(int i = 1; i <= n; ++i){ 
        id[i] = (i - 1) / B + 1;
        if(i <= k) a[i] = read(), has[i] = true, ++cnt[id[i]], sum += a[i];
    }
    for(int i = 1; i <= N; ++i){
        L[i] = (i - 1) * B + 1;
        R[i] = min(i * B, n);
    }

    auto opC = [&](int x, ll y) -> void {
        a[x] -= y; sum -= y;
    };

    auto opI = [&](int x, ll y) -> void {
        if(!has[x]){
            has[x] = true; ++cnt[id[x]];
            a[x] = y; sum += y;
        }
        else{
            sum -= a[x]; a[x] = y; sum += y;
        }
    };

    auto opD = [&](int x) -> void {
        int i = 1, tot = 0;
        while(tot + cnt[i] < x) tot += cnt[i++];
        x -= tot;
        for(int cur = L[i]; cur <= R[i]; ++cur){
            if(has[cur]) --x;
            if(!x){
                has[cur] = false; --cnt[id[cur]];
                sum -= a[cur]; a[cur] = 0;
                return;
            }
        }
    };

    for(int i = 1; i <= m; ++i){
        char op = ' ';
        while(op != 'C' and op != 'I' and op != 'D' and op != 'Q') op = getchar();
        if(op == 'Q') printf("%lld\n", sum);
        else if(op == 'C'){
            int x = read(); ll y = read();
            opC(x, y);
        }
        else if(op == 'D'){
            int x = read();
            opD(x);
        }
        else if(op == 'I'){
            int x = read(); ll y = read();
            opI(x, y);
        }
    }
}

int main(){
    solve();
}

总结

虽然分块在时间复杂度上往往劣于线段树, 但分块通用性更强, 可用于维护不具有可合并性的信息, 而且码量不大、常数较小、思想灵活(分块思想可应用到树、链表等结构上), 具有广泛的应用价值和重要的学习意义.

  • 标题: 算法学习笔记 -- 数列分块
  • 作者: Coast23
  • 创建于 : 2025-09-16 23:09:57
  • 更新于 : 2025-09-16 23:39:39
  • 链接: https://coast23.github.io/2025/09/16/算法学习笔记-数列分块/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
算法学习笔记 -- 数列分块
  1. 数列分块基本思想
  2. 数列分块代码框架
  3. 入门题集
    1. 1. 数列分块入门 1 [区间加法, 单点查询]
    2. 2. 数列分块入门 4 [区间加法, 区间求和]
    3. 3. 数列分块入门7 [区间加法, 区间乘法, 区间求和]
    4. 4. 数列分块入门8 [区间赋值, 值查询]
    5. 5. 数列分块入门5 [区间开方, 区间求和]
    6. 6. 数列分块入门2 [区间加法, 小于 的元素个数]
    7. 7. 教主的魔法 [区间加法, 大于等于 的个数]
    8. 8. 数列分块入门3 [区间加法, 查询前驱]
    9. 9. 数列分块入门9 [无修改, 查询区间最小众数]
    10. 10. [Violet] 蒲公英 [无修区间众数, 强制在线]
    11. 11. ycz的妹子
  4. 总结