树状数组及应用
目录
1.树状数组的概念与基本编码
1.1.引导
1.2.lowbit(x)
1.3.树状数组的编码
2.树状数组的基本应用
2.1.单点修改+区间查询
2.2.区间修改+单点查询
例题:
2.3.区间修改+区间查询
例题:
如果数列A是静态不变的,那么处理前缀和复杂度为O(n),查询为O(1),但如果序列是动态变化的,如改变其中一个元素,那么就需要重新计算前缀和,如果每次查询都有变化,那么复杂度会大幅度增加。
有两种数据结构可以高效的处理这个问题:树状数组与线段树。
1.树状数组的概念与基本编码
1.1.引导
如图所示,c[1] = A[1], c[2] = c[1] + A[2], c[3] = A[3], c[4] = c[2] + c[3] + A[4], ... , c[8] = c[4] + c[6] + c[7] + A[8]。
利用c数组可以高效的完成以下两个操作。
(1)查询,即求前缀和sum。
(2)维护,即元素a发生变化时,能以O()的高效率修改c[] 的值。
结论:
(1)查询过程是每次去掉二进制的最后一个1。例如,求sum[7]:
- sum[7] += c[7]
- 7的二进制是111,去掉最后一个1,得110,即c[6],所以sum[7] += c[6]
- 110,去掉最后一个1,得100,sum[7] += c[4]
- 100,去掉最后一个1就没有了
故sum[7] = c[7] + c[6] + c[4]
(2)维护的过程是每次在二进制最后的1上加1。例如,更新a[3]:
- 3的二进制是11,在最后一个1上加1,得100,所以修改c[4];
- 100,在最后一个1上加1,得1000,所以修改c[8];
- 继续修改c[16],c[32]...
树状数组的关键就是找到最后一个1。
1.2.lowbit(x)
lowbit(x) = x & (-x),功能为找到x的二进制数最后一个1。其原理是利用负数的补码,例如x = 6 = 000110, 补 = 111010,那么x & (-x) = 10 = 2;
lowbit(x) 部分结果如下:
x | x的二进制 | lowbit(x) | tree[x]数组 |
1 | 1 | 1 | tree[1] = a1 |
2 | 10 | 2 | tree[2] = a2 + a1 |
3 | 11 | 1 | tree[3] = a3 |
4 | 100 | 4 | tree[4] = a4 + a3+ a2+ a1 |
5 | 101 | 1 | tree[5] = a5 |
6 | 110 | 2 | tree[6] = a6 + a5 |
7 | 111 | 1 | tree[7] = a7 |
令m = lowbit(x),tree[x]的值是把和他前面共m个数相加的结果。
tree[]数组是通过lowbit计算出的树状数组,它能够以二分的复杂度存储一个数列的数据,具体的说,tree[x]存储的是区间[x - lowbit(x) + 1, x]的每个数的和。
1.3.树状数组的编码
下面给出单点修改+区间查询的代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(x) (x & (-x))
const int N = 1000;
int tree[N];
void update(int x, int d) {//单点修改,修改玄素a[x],a[x] = a[x] + dwhile (x <= N) {tree[x] += d;x += lowbit(x);}
}
ll sum(int x) {//查询前缀和:返回前缀和sum = a[1] + a[2] + .., + a[x]ll ans = 0;while (x > 0) {ans += tree[x];x -= lowbit(x);}return ans;
}
void solve() {int n;cin >> n;vector<ll> a(n + 1, 0);//a[0]不用memset(tree, 0, sizeof(tree));for (int i = 1; i <= n; i++) {cin >> a[i];update(i, a[i]);}//查询区间和:cout << "Old : sum([1,n-1]):" << sum(n - 1) - sum(0) << endl;//模拟一次修改,a[n-1] + 100update(n - 1, 100);cout << "New : sum([1,n-1]):" << sum(n - 1) - sum(0) << endl;
}
int main() {ios::sync_with_stdio;cin.tie(0);cout.tie(0);solve();return 0;
}
/*
输入:
10
4 5 6 7 8 9 10 11 12 13
输出:
Old : sum([1,n-1]):72
New : sum([1,n-1]):172
*/
此代码过程:
(1)初始化:先清空数组tree,然后读取a数组每一个元素,用update() 逐步处理这n个数,得到tree[]数组;
(2)求前缀和:用sum()计算,求和基于tree数组;
(3)单点修改:执行update()函数,修改数组tree[]。
2.树状数组的基本应用
2.1.单点修改+区间查询
1.1.3.树状数组的编码已经给出
2.2.区间修改+单点查询
利用差分是前缀和的逆运算来求解
例题:
两种解法:
第一种,单纯的差分数组
#include<bits/stdc++.h>
using namespace std;
int n, a, b, diff[100002];
int main() {ios::sync_with_stdio(false);cin.tie(0);while (cin >> n && n != 0) {for (int i = 0; i <= n; i++) {diff[i] = 0;}for (int i = 0; i < n; i++) {cin >> a >> b;diff[a] += 1;diff[b + 1] -= 1;}diff[1] += diff[0];cout << diff[1];for (int i = 2; i <= n; i++) {diff[i] += diff[i - 1];cout << ' ' << diff[i];}}return 0;
}
第二种,利用树状数组
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(x) (x & (-x))
const int N = 100010;
int tree[N];
void update(int x, int d) {while (x <= N) {tree[x] += d;x += lowbit(x);}
}
ll sum(int x) {ll ans = 0;while (x > 0) {ans += tree[x];x -= lowbit(x);}return ans;
}
void solve() {int n;while (cin >> n && n != 0) {memset(tree, 0, sizeof(tree));for (int i = 1; i <= n; i++) {int L, R;cin >> L >> R;update(L, 1);update(R + 1, -1);}for (int i = 1; i <= n; i++) {if (i != n)cout << sum(i) << ' ';else cout << sum(i) << endl;}}
}
int main() {ios::sync_with_stdio;cin.tie(0);cout.tie(0);solve();return 0;
}
2.3.区间修改+区间查询
完成区间修改需要一个tree,区间查询也需要一个tree,所以可以利用两个tree达成此要求
=
=
所以可以分别处理d和(i-1)d两个数组的树状数组
例题:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(x) (x & (-x))
const int N = 100010;
ll tree1[N], tree2[N];
void update1(ll x, ll d) {while (x <= N) {tree1[x] += d;x += lowbit(x);}
}
ll sum1(ll x) {ll ans = 0;while (x > 0) {ans += tree1[x];x -= lowbit(x);}return ans;
}
void update2(ll x, ll d) {while (x <= N) {tree2[x] += d;x += lowbit(x);}
}
ll sum2(ll x) {ll ans = 0;while (x > 0) {ans += tree2[x];x -= lowbit(x);}return ans;
}
void solve() {ll n, m;memset(tree1, 0, sizeof(tree1));memset(tree2, 0, sizeof(tree2));cin >> n >> m;ll old = 0, a;for (int i = 1; i <= n; i++) {cin >> a;update1(i, a - old);update2(i, (i - 1) * (a - old));old = a;}while (m--) {ll q, L, R, d;cin >> q;if (q == 1) {cin >> L >> R >> d;update1(L, d);update1(R + 1, -d);update2(L, (L - 1) * d);update2(R + 1, -R * d);}else {cin >> L >> R;cout << R * sum1(R) - sum2(R) - (L - 1) * sum1(L - 1) + sum2(L - 1) << endl;}}
}
int main() {ios::sync_with_stdio;cin.tie(0);cout.tie(0);solve();return 0;
}