【算法】分块

背景

更具一般性的区间算法。

介绍

我们将数列分成若干个长度不超过$\lfloor\sqrt N\rfloor$的块,显然第$i$段的左端点为$(i-1)\lfloor\sqrt N\rfloor +1$,右端点为$\min \left(i\lfloor\sqrt N\rfloor,N\right)$,当然,这里是从$1$开始计数的情况下定义的。

通用的分块方式

int sqr = sqrt(n);
for(int i = 1;i <= sqr;i++) L[i] = (i - 1) * sqr + 1,R[i] = i * sqr;
if(R[sqr] < n) sqr++,L[sqr] = R[sqr - 1] + 1,R[sqr] = n;
for(int i = 1;i <= sqr;i++)
    for(int j = L[i];j <= R[i];j++)
        pos[j] = i;

$L[],R[]$分别记录了每段左右端点,$pos[]$则可快速查询某数属于哪一段。

分块入门-1

来自hzwer.com

给出一个长为n的数列,以及n个操作,操作涉及区间加法,单点查值

这个过于容易就直接贴代码,统计一个加法标记,分块即可

代码
#include<cstdio>
#include<cmath>
namespace IO{
    inline int read(){
        int ans = 0,op = 1;char s = getchar();
        while(s < '0' || s > '9'){if(s == '-'){op = -1;}s = getchar();}
        while(s >= '0' && s <= '9'){ans = ans * 10 + s - '0';s = getchar();}
        return ans *= op;
    }
    void print(int x){
        if(x < 0) putchar('-'),x = -x;
        if(x > 9) print(x / 10);
        putchar(x % 10 + '0');
    }
    void println(int x){
        print(x);putchar('\n');
    }
}
using namespace IO;

const int MAXN = 50000 + 666;
int LEFT[MAXN],RIGHT[MAXN],pos[MAXN],add[MAXN],A[MAXN];

void plus(int l,int r,int d){
    int p = pos[l],q = pos[r];
    if(p == q){for(int i = l;i <= r;i++) A[i] += d;
    }else{
        for(int i = p + 1;i <= q - 1;i++) add[i] += d;
        for(int i = l;i <= RIGHT[p];i++) A[i] += d;
        for(int i = LEFT[q];i <= r;i++) A[i] += d;
    }
}

int main(){
    int n = read();
    for(int i = 1;i <= n;i++) A[i] = read();

    int sqr = sqrt(n);
    for(int i = 1;i <= sqr;i++) LEFT[i] = (i - 1) * sqr + 1,RIGHT[i] = i * sqr;
    if(RIGHT[sqr] < n) sqr++,LEFT[sqr] = RIGHT[sqr - 1] + 1,RIGHT[sqr] = n;
    for(int i = 1;i <= sqr;i++){
        for(int j = LEFT[i];j <= RIGHT[i];j++) pos[j] = i;
    }

    int op,l,r,c;
    while(n--){
        op = read();l = read();r = read();c = read();
        if(op == 0) plus(l,r,c);
        else println(A[r] + add[pos[r]]);
    }

    return 0;
}