树状数组
- 时间复杂度：O（n）
- 适用于：单点更新，区间查询
理解
C[1] = C[0001] = A[1]; C[2] = C[0010] = A[1]+A[2]; C[3] = C[0011] = A[3]; C[4] = C[0100] = A[1]+A[2]+A[3]+A[4]; C[5] = C[0101] = A[5]; C[6] = C[0110] = A[5]+A[6]; C[7] = C[0111] = A[7]; C[8] = C[1000] = A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];
即：
- $C[i]=A[i-2^k+1]+A[i-2^k+2]+\dots+A[i];$
- $k$为 $i$ 的二进制中从最低位到高位连续零的长度。
- $2^k$可通过$i&-i$获得。
补码为原码取反后加1，如果将补码+1进位，那么最末尾的1和原码最右边的1一定是同一个位置
lowbit
1
2
3inline int lowbit(x){
return x&(-x);
}
单点更新
1
2
3
4
5
6
7
8
9
10void update(int *arr,int index,int diff,int len){
/*
* arr：树状数组
* index：待更新的位置
* diff：改变的值
* len：树状数组长度
*/
for(int i=index;i<=len;i+=lowbit(i))
arr[i] += diff;
}
区间查询
1
2
3
4
5
6
7
8
9
10int getsum(int *arr,int x){
/*
* arr：树状数组
* x：求从1到x的和
*/
int ans = 0;
for(int i=x;i;i-=lowbit(i))
ans += arr[i];
return ans;
}
样例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
using namespace std;
int lowbit(const int t) {
return t & (-t);
}
void insert(int t, int d) {
while (t <= n){
a[t] += d;
t = t + lowbit(t);
}
}
int getSum(int t) {
int sum = 0;
while (t > 0){
sum += a[t];
t = t - lowbit(t);
}
return sum;
}
int main() {
int t, k, d;
scanf("%d", &t);
k= 1;
while (t--){
memset(a, 0, sizeof(a));
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &d);
insert(i, d);
}
string str;
printf("Case %d:\n", k++);
while (cin >> str) {
if (str == "End") break;
int x, y;
scanf("%d %d", &x, &y);
if (str == "Query")
printf("%lld\n", getSum(y) - getSum(x - 1));
else if (str == "Add")
insert(x, y);
else if (str == "Sub")
insert(x, -y);
}
}
return 0;
}
线段树
模板一、RMQ，查询区间最值下标
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
using namespace std;
//构建线段树,目的:得到M数组.
void build(int node, int b, int e, int M[], int A[])
{
if (b == e)
M[node] = b; //只有一个元素,只有一个下标
else
{
build(2 * node, b, (b + e) / 2, M, A);
build(2 * node + 1, (b + e) / 2 + 1, e, M, A);
if (A[M[2 * node]] <= A[M[2 * node + 1]])
M[node] = M[2 * node];
else
M[node] = M[2 * node + 1];
}
}
//找出区间 [i, j] 上的最小值的索引
int query(int node, int b, int e, int M[], int A[], int i, int j)
{
int p1, p2;
//查询区间和要求的区间没有交集
if (i > e || j < b)
return -1;
if (b >= i && e <= j)
return M[node];
p1 = query(2 * node, b, (b + e) / 2, M, A, i, j);
p2 = query(2 * node + 1, (b + e) / 2 + 1, e, M, A, i, j);
//return the position where the overall
//minimum is
if (p1 == -1)
return M[node] = p2;
if (p2 == -1)
return M[node] = p1;
if (A[p1] <= A[p2])
return M[node] = p1;
return M[node] = p2;
}
int main()
{
int M[MAXIND]; //下标1起才有意义,否则不是二叉树,保存下标编号节点对应区间最小值的下标.
memset(M,-1,sizeof(M));
int a[]={3,4,5,7,2,1,0,3,4,5};
build(1, 0, sizeof(a)/sizeof(a[0])-1, M, a);
cout<<query(1, 0, sizeof(a)/sizeof(a[0])-1, M, a, 0, 5)<<endl;
return 0;
}
模板二、连续区间修改或者单节点更新的动态查询问题 （此模板查询区间和）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
using namespace std;
const int maxn = 111111;
LL add[maxn<<2];
LL sum[maxn<<2];
void PushUp(int rt) {
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void PushDown(int rt,int m) {
if (add[rt]) {
add[rt<<1] += add[rt];
add[rt<<1|1] += add[rt];
sum[rt<<1] += add[rt] * (m - (m >> 1));
sum[rt<<1|1] += add[rt] * (m >> 1);
add[rt] = 0;
}
}
void build(int l,int r,int rt) {
add[rt] = 0;
if (l == r) {
scanf("%lld",&sum[rt]);
return ;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
PushUp(rt);
}
void update(int L,int R,int c,int l,int r,int rt) {
if (L <= l && r <= R) {
add[rt] += c;
sum[rt] += (LL)c * (r - l + 1);
return ;
}
PushDown(rt , r - l + 1);
int m = (l + r) >> 1;
if (L <= m) update(L , R , c , lson);
if (m < R) update(L , R , c , rson);
PushUp(rt);
}
LL query(int L,int R,int l,int r,int rt) {
if (L <= l && r <= R) {
return sum[rt];
}
PushDown(rt , r - l + 1);
int m = (l + r) >> 1;
LL ret = 0;
if (L <= m) ret += query(L , R , lson);
if (m < R) ret += query(L , R , rson);
return ret;
}
int main() {
int N , Q;
scanf("%d%d",&N,&Q);
build(root);
while (Q --) {
char op[2];
int a , b , c;
scanf("%s",op);
if (op[0] == 'Q') {
scanf("%d%d",&a,&b);
printf("%lld\n",query(a , b ,root));
} else {
scanf("%d%d%d",&a,&b,&c);
update(a , b , c , root);
}
}
return 0;
}
前缀和
一维前缀和
有数组A，数组A对应的前缀和数组为S，有： $$ S[k]=\sum_{i=0}^{k}A[i] $$
由此方便了范围查询： $$ \sum_{i=L}^RA[i]=S[R]-S[L-1] $$
二维前缀和
对于二维数组A，数组A对应的前缀和数组为S，有： $$ S[i][j]=\sum_{m=0}^i\sum_{n=0}^jA[i][j] $$ 计算时二维前缀和时，可以使用递推公式： $$ S[i][j]=A[i][j]+S[i-1][j]+S[i][j-1]-S[i-1][j-1] $$ 当求被点$(x_1,y_1)$和点$(x_2,y_2)$围起来的元素的和时，可以使用： $$ \sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2}A[i][j]=S[x_2][y_2]-S[x_1-1][y2]-S[x_2][y_1-1]+S[x_1-1][y_1-1] $$
差分
差分可解决范围更新的问题。
思想：
- 延后更新
- 更新的起点和终点
- 利用前缀和
样例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
using namespace std;
const int maxn=1e5+9;
int a[maxn],b[maxn];
int main(){
int i,j,k,n,m,p;
cin>>n>>m;
for(i=1;i<=n;i++){
cin>>a[i];
}
for(i=1;i<=m;i++){
int L,R,t;
cin>>t>>L>>R>>p;
if(t==1){
b[L]+=p;b[R+1]-=p;
}
else{
b[L]-=p;b[R+1]+=p;
}
}
int add=0;
for(i=1;i<=n;i++){
add+=b[i];
a[i]+=a[i-1]+add;
}
int x,y;
cin>>x>>y;
cout<<a[y]-a[x-1]<<endl;
}