模板及讲解
维护区间$[1, n]$的数据结构，可以用$[1, b]-[1, a]$来求$[a,b]$
可以$add(a, x), add(b+1, -x)$实现区间修改单点查询(差分序列求前缀和优化到$logn$)
二维树状数组(容斥原理)
区间修改区间查询
设原数组为$a_i$，原数组差分序列为$d_i$，$x$为查询区间$[1,x]$，则
$$a_x=\sum_{i=1}^x d_i$$
则
$$\sum_{i=1}^x a_i= \sum_{i=1}^x \sum_{j=1}^i d_j =\sum_{i=1}^x(x-i+1)d_i$$
那么
$$\sum_{i=1}^x a_i=(x+1)\sum_{i=1}^x d_i-\sum_{i=1}^x d_i \times i$$
这样我们维护两个树状数组，一个维护$d_i$，一个维护$d_i \times i$，每次查询修改对两个树状数组进行操作即可。(常数比线段树小)
单点修改区间最大值
Bzoj 1012
$c[i]$维护$[i-\operatorname{lowbit}(i)+1,i]$的最大值，$a[i]$为原数组
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
LL m, D, x, cnt, lastans = 0;
LL a[200000 + 5], c[200000 + 5]; // c[i]维护[i-lowbit(i)+1,i]的最大值，a[i]为原数组
char s[5];
LL lowbit(LL x) {return x & (-x);}
LL query(LL l, LL r) {
LL ret = a[r];
while (l <= r) {
ret = max(ret, a[r]);
for (--r; r - l >= lowbit(r); r -= lowbit(r))
ret = max(ret, c[r]);
}
return ret;
}
void clean() {
cnt = 0, ms(a, 0), ms(c, 0);
}
int solve() {
clean();
cin >> m >> D;
for (LL i = 1; i <= m; ++i) {
scanf("%s%lld", s, &x);
if (s[0] == 'A') {
a[++cnt] = (x + lastans) % D;
c[cnt] = max(a[cnt], query(cnt - lowbit(cnt) + 1, cnt));
} else {
printf("%lld\n", lastans = query(cnt - x + 1, cnt));
}
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
树状数组求$k$大
LL C[MAXN];
void update(LL x) {while (x <= m) C[x]++, x += x & (-x);}
LL query(LL x) {
LL p = 0;
for (LL i = 20; ~i; --i) {
if (p + (1 << i) <= m && C[p + (1 << i)] <= x) x -= C[p + (1 << i)], p += (1 << i);
}
return p;
}