树状数组处理区间问题
树状数组是解决动态前缀和问题的数据结构，大佬们总是把ST表，树状数组，线段树三个东西联系在一起，都是用于解决动态区间问题的方法。
树状数组是2的次方前缀和数组，像树一样，如图所示，每个位置 i 的前缀和长度为 lowbit（i），而每层之间深度所差的区间长度也为lowbit（i），例如要对 t[4] +1，则其后面的包含 t[4] 的 t[8]也进行+1。
因此当我们要求 6的前缀和，因该是6所包含的区间加上6包含区间的前面的区间，即是 t[4] + t[6]。
若求 3 到 6的区间和时，便是 前缀和 6 - 前缀和 2，而 前缀和 6 = t[6] + t[4] ，所以3 到 6 的区间和便是 t[6] + t[4] - t[2]
单点加值：
1
2
3
4
5
|
void add(int a,int b){
for(int i=a;i<=n;i+=lowbit(i))
t[i]+=b;
}
|
前缀和：
1
2
3
4
5
6
7
8
|
int sum(int x){
int ans=0;
for(int i=x;i>0;i-=lowbit(i))
ans+=t[i];
return ans;
}
|
下面就是单点改值和区间和查询的问题
P3374 【模板】树状数组 1 - 洛谷 | 计算机科学教育新生态
题目描述
如题，已知一个数列，你需要进行下面两种操作：
输入格式
第一行包含两个正整数 n,m，分别表示该数列数字的个数和操作的总个数。
第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。
接下来 m 行每行包含 3 个整数，表示一个操作，具体如下：
这样子这道题就变得显而易见了
lowbit(x) 的返回值是x二进制最小位1，所以返回的是x&-x，这里我用宏定义
对于lowbit(x), 我们从已学的计算机理论知识中得知计算机对两个数进行计算时,是将其转换为补码进行运算,而正数的补码又是其本身.
假设我们有一个整数 x=(01010)B, 我们有以下操作
$ x = (0 1 0 1 0)_B$ // x 的原码表示
−x=(11010)B //-x 的原码表示
−x=(10110)B //-x 的补码表示
$ x & (x) = $ //x 与 -x 按位与
$ (0 1 0 1 0)_B$ //x 的补码
& (10110)B //-x 的补码
= (00010)B //按位与后的补码(同时也是原码)
于是我们便可以得出x在二进制位下最小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
30
31
32
33
34
35
36
37
38
| #include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<=m;++i)
#define per(i,n,m) for(int i=n;i>=m;--i)
#define PII pair<int,int>
#define lowbit(x) x&-x
#define INF 1<<30
using namespace std;
typedef long long ll;
const int N=5e5+10;
int t[N],n,q;
void add(int a,int b){
for(int i=a;i<=n;i+=lowbit(i))t[i]+=b;
}
int sum(int x){
int ans=0;
前面每一段区间和
for(int i=x;i>0;i-=lowbit(i))ans+=t[i];
return ans;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>q;
rep(i,1,n){
int x;cin>>x;
add(i,x);
}
while(q--){
int a,b,c;cin>>a>>b>>c;
if(a==1)
add(b,c);
else
cout<<sum(c)-sum(b-1)<<endl;
}
return 0;
}
|
还有区间改值和单点查询的问题，
P3368 【模板】树状数组 2 - 洛谷 | 计算机科学教育新生态
题目描述
如题，已知一个数列，你需要进行下面两种操作：
输入格式
第一行包含两个整数 N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含 N 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。
接下来 M 行每行包含 2 或 4 个整数，表示一个操作，具体如下：
操作 1： 格式：1 x y k 含义：将区间 [x,y] 内每个数加上 k；
操作 2： 格式：2 x 含义：输出第 x 个数的值。
1
2
3
4
5
| 下标i 0 1 2 3 4 5 6 7
原数值a 0 1 2 1 -2 4 9 0
差分值b 0 1 1 -1 -3 6 5 -9
|
对于区间改值后的区间和，我们知道可以用差分做，那差分是什么呢，
差分 b[i] 就是 a[i] - a[i-1] ，而 a[n] 可以用 表示（哈哈哈，公式好大个），当区间 [l，r] 内+x时，只需 b[l] +x，b[r+1] -x，即可保证只有区间内值增加
对于该题，我们不妨初始化差分数组为0，然后使次区间改值时对差分数组边界进行两次操作
最后的单点查询就是改变的差分值加上原数值，即 sum(x) + a[x]
（以下用t数组代表差分数组，q数组表示原数值数组）
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
| #include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<=m;++i)
#define per(i,n,m) for(int i=n;i>=m;--i)
#define PII pair<int,int>
#define lowbit(x) x&-x
#define INF 1<<30
using namespace std;
typedef long long ll;
const int N=5e5+10;
int q[N],t[N],n,T;
void add(int a,int b){
for(int i=a;i<=n;i+=lowbit(i))t[i]+=b;
}
int sum(int x){
int ans=0;
for(int i=x;i>0;i-=lowbit(i))ans+=t[i];
return ans;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>T;
rep(i,1,n)cin>>q[i];
while(T--){
int x,a,b,c;cin>>x;
if(x==1){
cin>>a>>b>>c;
add(a,c);
add(b+1,-c);
}else {
cin>>a;
cout<<sum(a)+q[a]<<endl;
}
}
return 0;
}
|
对于某些会越界的样例，必要时要int改long long。
今天刚学，有点囫囵吞枣，描述的不太清楚。
