参考：「分块」数列分块入门1 – 9 by hzwer
1
Description
给出一个长为(n)的数列，以及(n)个操作，操作涉及区间加法，单点查值。
思路
用(tag)记录每个块整体的增量。
Code
#include <bits/stdc++.h>
#define maxn 50010
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
typedef long long LL;
int n, blo, a[maxn], tag[maxn], bl[maxn];
void add(int l, int r, int c) {
F2(i, l, min((bl[l]+1)*blo-1, r)) a[i] += c;
if (bl[l] != bl[r]) {
F2(i, bl[r]*blo, r) a[i] += c;
}
F2(i, bl[l]+1, bl[r]-1) tag[i] += c;
}
int main() {
scanf("%d", &n); blo = sqrt(n);
F(i, 0, n) scanf("%d", &a[i]), bl[i] = i / blo;
F(i, 0, n) {
int op, l, r, c;
scanf("%d%d%d%d", &op, &l, &r, &c); --l, --r;
if (op) printf("%d
", a[r]+tag[bl[r]]);
else add(l, r, c);
}
return 0;
}
4
Description
给出一个长为(n)的数列，以及(n)个操作，操作涉及区间加法，区间求和。
思路
法一：树状数组
(delta)差分数组：(delta[i])记录([i,n])整体的增量。
则$$egin{aligned}sum[x]&=sum_{i=1}{x}a_i+sum_{i=1}{x}d_i(x-i+1)&=sum_{i=1}{x}a_i+(x+1)*sum_{i=1}{x}d_i-sum_{i=1}^{x}id_iend{aligned}$$
维护三个树状数组即可。
法二：分块
用(tag)记录每个块整体的增量。
用(sum)维护每个块的和。
Code
Ver. 1
#include <bits/stdc++.h>
#define maxn 50010
#define F(i, a, b) for (LL i = (a); i < (b); ++i)
#define F2(i, a, b) for (LL i = (a); i <= (b); ++i)
#define dF(i, a, b) for (LL i = (a); i > (b); --i)
#define dF2(i, a, b) for (LL i = (a); i >= (b); --i)
using namespace std;
typedef long long LL;
LL n, x, v[maxn], d[maxn], D[maxn];
inline LL lowbit(LL x) { return x & (-x); }
inline LL sum(LL* a, LL x, LL mod) { LL ret = 0; while (x) (ret += a[x]) %= mod, x -= lowbit(x); return ret; }
inline void add(LL* a, LL x, LL c) { while (x<=n) a[x] += c, x += lowbit(x); }
inline LL query(LL x, LL mod) {
return ((sum(v, x, mod) + (x+1) * sum(d, x, mod) % mod) % mod + mod - sum(D, x, mod)) % mod;
}
inline void modify(LL l, LL r, LL c) {
add(d, l, c), add(d, r+1, -c);
add(D, l, c*l), add(D, r+1, -c*(r+1));
}
int main() {
scanf("%lld", &n);
F2(i, 1, n) scanf("%lld", &x), add(v, i, x);
F(i, 0, n) {
LL op, l, r, c, mod;
scanf("%lld%lld%lld%lld", &op, &l, &r, &c); mod=c+1;
if (op) printf("%lld
", (query(r,mod)+mod-query(l-1,mod))%mod);
else modify(l, r, c);
}
return 0;
}
Ver. 2
#include <bits/stdc++.h>
#define maxn 50010
#define F(i, a, b) for (LL i = (a); i < (b); ++i)
#define F2(i, a, b) for (LL i = (a); i <= (b); ++i)
#define dF(i, a, b) for (LL i = (a); i > (b); --i)
#define dF2(i, a, b) for (LL i = (a); i >= (b); --i)
using namespace std;
typedef long long LL;
LL blo, a[maxn], bl[maxn], sum[maxn], tag[maxn];
void modify(LL l, LL r, LL c) {
F(i, l, min((bl[l]+1)*blo, r+1)) a[i] += c;
sum[bl[l]] += c * (min((bl[l]+1)*blo,r+1) - l);
if (bl[l]!=bl[r]) {
F2(i, bl[r]*blo, r) a[i] += c;
sum[bl[r]] += c * (r+1 - bl[r]*blo);
}
F(i, bl[l]+1, bl[r]) tag[i] += c, sum[i] += c * blo;
}
LL query(LL l, LL r, LL mod) {
LL ret=0;
F(i, l, min((bl[l]+1)*blo, r+1)) (ret += a[i]) %= mod;
(ret += tag[bl[l]] * (min((bl[l]+1)*blo,r+1) - l) % mod) %= mod;
if (bl[l] != bl[r]) {
F2(i, bl[r]*blo, r) (ret += a[i]) %= mod;
(ret += tag[bl[r]] * (r+1 - bl[r]*blo) % mod) %= mod;
}
F(i, bl[l]+1, bl[r]) (ret += sum[i]) %= mod;
return ret;
}
int main() {
LL n;
scanf("%lld", &n); blo = sqrt(n);
F(i, 0, n) scanf("%lld", &a[i]), bl[i] = i/blo;
LL num = (n+blo-1) / blo;
F(i, 0, num-1) {
F(j, i*blo, (i+1)*blo) sum[i] += a[j];
}
F(j, (num-1)*blo, min(num*blo, n+1)) sum[num-1] += a[j];
F(i, 0, n) {
LL op, l, r, c;
scanf("%lld%lld%lld%lld", &op, &l, &r, &c); --l, --r;
if (op) printf("%lld
", query(l, r, c+1));
else modify(l, r, c);
}
return 0;
}