三类BIT

三类BIT的总结

BIT

  1. 单点修改,求区间的和。
  2. 区间修改,询问单点的值。
  3. 区间修改,区间查询

单点修改,查询区间和

区间修改,查询单点的值

区间修改,区间查询

poj 3468

原理就是增加了两个数组,维护不同的属性。
操作和树状数组完全一样。

ac code

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[maxn], n, m;
typedef long long ll;
ll s[maxn], c[2][maxn];
int lowbit(int x){
return (x&(-x));
}
ll ask(int k, int x){
ll ans = 0;
while(x>0){
ans += c[k][x];
x -= lowbit(x);
}
return ans;
}
void add(int k, int x, int val){
while(x<=n){
c[k][x] += val;
x += lowbit(x);
}
}
int main()
{
ios::sync_with_stdio(false);
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
s[i] = s[i-1]+a[i];
}
while(m--){
//cout<<"tets"<<m<<endl;
char op[2];
int l, r, d;
scanf("%s%d%d", op, &l, &r);
if(op[0] == 'C'){
scanf("%d", &d);
//cout<<l<<" "<<r<<" "<<d<<endl;
add(0, l, d);
add(0, r+1, -d);
add(1, l, l*d);
add(1, r+1, -(r+1)*d);
//cout<<"hehe"<<endl;
}
else{
ll ans = s[r]+(r+1)*ask(0, r)-ask(1, r);
ans -= s[l-1]+l*ask(0, l-1)-ask(1, l-1);
printf("%d\n", ans);
}
}
return 0;
}

未解决的问题

文章目录
  1. 1. BIT
  2. 2. 单点修改,查询区间和
  3. 3. 区间修改,查询单点的值
  4. 4. 区间修改,区间查询
    1. 4.1. poj 3468
      1. 4.1.1. ac code
  5. 5. 未解决的问题
{{ live2d() }}