时间戳

首页 > 技术文章 > 【数据结构】分块

【数据结构】分块

purinliang 2020-09-15 12:56 原文

单点修改，区间求和

已验证：
https://www.luogu.com.cn/problem/P3374 （单点修改，区间求和）

rt[i]: i位置所属的块的序号
va[i]: i位置的值
lb[b]: 序号b的块的左边界的位置
rb[b]: 序号b的块的左边界的位置
sm[b]: 序号b的块的区间求和

struct Block {

    static const int MAXN = 500000 + 5;
    static const int MAXB = 500000 + 5;

    int rt[MAXN];
    ll va[MAXN];
    int lb[MAXB];
    int rb[MAXB];
    ll sm[MAXB];

    void Add(int x, ll v) {
        va[x] += v;
        sm[rt[x]] += v;
    }

    ll Sum(int l, int r) {
        if(rt[l] == rt[r]) {
            ll res = 0LL;
            for(int i = l; i <= r; ++i)
                res += va[i];
            return res;
        } else {
            ll res = 0LL;
            for(int i = l; i <= rb[rt[l]]; ++i)
                res += va[i];
            for(int i = lb[rt[r]]; i <= r; ++i)
                res += va[i];
            for(int b = rt[l] + 1; b <= rt[r] - 1; ++b)
                res += sm[b];
            return res;
        }
    }

    void Init(int n) {
        int blk = (int)sqrt(n) + 1;
        int cntblk = (n + blk - 1) / blk;
        memset(va, 0LL, sizeof(va[0]) * (n + 1));
        memset(lb, INF, sizeof(lb[0]) * (cntblk + 1));
        memset(rb, -INF, sizeof(rb[0]) * (cntblk + 1));
        memset(sm, 0LL, sizeof(sm[0]) * (cntblk + 1));
        for(int i = 1; i <= n; ++i) {
            rt[i] = (i + blk - 1) / blk;
            lb[rt[i]] = min(lb[rt[i]], i);
            rb[rt[i]] = max(rb[rt[i]], i);
        }
    }

} blk;

区间修改，单点求值

已验证：
https://www.luogu.com.cn/problem/P3368 （区间修改，单点求值）

rt[i]: i位置所属的块的序号
va[i]: i位置的值
lb[b]: 序号b的块的左边界的位置
rb[b]: 序号b的块的左边界的位置
lz[b]: 序号b的块的懒惰标记

struct Block {

    static const int MAXN = 500000 + 5;
    static const int MAXB = 500000 + 5;

    int rt[MAXN];
    int va[MAXN];
    int lb[MAXB];
    int rb[MAXB];
    int lz[MAXB];

    void Add(int l, int r, int v) {
        if(rt[l] == rt[r]) {
            for(int i = l; i <= r; ++i)
                va[i] += v;
        } else {
            for(int i = l; i <= rb[rt[l]]; ++i)
                va[i] += v;
            for(int i = lb[rt[r]]; i <= r; ++i)
                va[i] += v;
            for(int b = rt[l] + 1; b <= rt[r] - 1; ++b)
                lz[b] += v;
        }
    }

    int Val(int x) {
        return va[x] + lz[rt[x]];
    }

    void Init(int n) {
        int blk = (int)sqrt(n) + 1;
        int cntblk = (n + blk - 1) / blk;
        memset(va, 0, sizeof(va[0]) * (n + 1));
        memset(lb, INF, sizeof(lb[0]) * (cntblk + 1));
        memset(rb, -INF, sizeof(rb[0]) * (cntblk + 1));
        memset(lz, 0, sizeof(lz[0]) * (cntblk + 1));
        for(int i = 1; i <= n; ++i) {
            rt[i] = (i + blk - 1) / blk;
            lb[rt[i]] = min(lb[rt[i]], i);
            rb[rt[i]] = max(rb[rt[i]], i);
        }
    }

} blk;

区间修改，区间求和

区间修改多出一个懒惰标记。

已验证：
https://www.luogu.com.cn/problem/P3374 （单点修改，区间求和）
https://www.luogu.com.cn/problem/P3368 （区间修改，单点求值）
https://www.luogu.com.cn/problem/P3372 （区间修改，区间求和）

rt[i]: i位置所属的块的序号
va[i]: i位置的值
lb[b]: 序号b的块的左边界的位置
rb[b]: 序号b的块的左边界的位置
sm[b]: 序号b的块的区间求和
lz[b]: 序号b的块的懒惰标记

struct Block {

    static const int MAXN = 500000 + 5;
    static const int MAXB = 500000 + 5;

    int rt[MAXN];
    ll va[MAXN];
    int lb[MAXB];
    int rb[MAXB];
    ll sm[MAXB];
    ll lz[MAXB];

    void Add(int l, int r, ll v) {
        if(rt[l] == rt[r]) {
            for(int i = l; i <= r; ++i)
                va[i] += v;
            sm[rt[l]] += v * (r - l + 1);
        } else {
            for(int i = l; i <= rb[rt[l]]; ++i)
                va[i] += v;
            sm[rt[l]] += v * (rb[rt[l]] - l + 1);
            for(int i = lb[rt[r]]; i <= r; ++i)
                va[i] += v;
            sm[rt[r]] += v * (r - lb[rt[r]] + 1);
            for(int b = rt[l] + 1; b <= rt[r] - 1; ++b) {
                sm[b] += v * (rb[b] - lb[b] + 1);
                lz[b] += v;
            }
        }
    }

    ll Sum(int l, int r) {
        if(rt[l] == rt[r]) {
            ll res = 0LL;
            for(int i = l; i <= r; ++i) {
                res += va[i];
                res += lz[rt[i]];
            }
            return res;
        } else {
            ll res = 0LL;
            for(int i = l; i <= rb[rt[l]]; ++i)
                res += va[i];
            res += lz[rt[l]] * (rb[rt[l]] - l + 1);
            for(int i = lb[rt[r]]; i <= r; ++i)
                res += va[i];
            res += lz[rt[r]] * (r - lb[rt[r]] + 1);
            for(int b = rt[l] + 1; b <= rt[r] - 1; ++b)
                res += sm[b];
            return res;
        }
    }

    void Init(int n) {
        int blk = (int)sqrt(n) + 1;
        int cntblk = (n + blk - 1) / blk;
        memset(va, 0LL, sizeof(va[0]) * (n + 1));
        memset(lb, INF, sizeof(lb[0]) * (cntblk + 1));
        memset(rb, -INF, sizeof(rb[0]) * (cntblk + 1));
        memset(sm, 0LL, sizeof(sm[0]) * (cntblk + 1));
        memset(lz, 0LL, sizeof(lz[0]) * (cntblk + 1));
        for(int i = 1; i <= n; ++i) {
            rt[i] = (i + blk - 1) / blk;
            lb[rt[i]] = min(lb[rt[i]], i);
            rb[rt[i]] = max(rb[rt[i]], i);
        }
    }

} blk;

推荐阅读