acwing算法提高之数据结构--树状数组

1 介绍

本专题用来记录树状数组相关题目。

lowbit(x)操作，求数 x二进制表示中最低位的1的值，

int lowbit(int x) {return x & -x;
}

树状数组：用来快速计算动态前缀和的数据结构。

c[x]的表示原数组以第x个数结尾，且区间长度为lowbit(x)的区间的和，即c[x - lowbit(x) + 1] ~ c[x]。

在这里插入图片描述

树状数组支持两种操作：

单点修改，比如a[i] += x
区间查询，比如求a[l~r]的和

见上图，修改a[5]的值，则需要递次修改c[5], c[6], c[8]的值。那么修改操作的代码如下，

//a[x] += k
void add(int x, int k) {while (x <= n) {  // 不能越界。n就是最大值，总共n个数，编号分别为1,2,3...,nc[x] = c[x] + k;x = x + lowbit(x);}
}//或可以写成
void add(int x, int k) {for (int i = x; i <= n; i += lowbit(i)) {c[i] += k;}
}

见上图，查询前缀和a[1~5]，则需要递次遍历c[5], c[4], c[0]，将它们的值累加就是前缀和。那么求前缀和的代码如下，

int getsum(int x) {  // a[1]..a[x]的和int ans = 0;while (x >= 1) {ans = ans + c[x];x = x - lowbit(x);}return ans;
}//或可以写成
int getsum(int x) {int ans = 0;for (int i = x; i >= 1; i -= lowbit(i)) {ans += c[i];}return ans;
}

2 训练

题目1：241楼兰图腾

C++代码如下，

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 200010;int n;
int a[N]; //a[x] = 2表示数x出现了2次
int tr[N];
int Greater[N], lower[N];int lowbit(int x) {return x & -x;
}void add(int x, int c) {for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}int sum(int x) {int res = 0;for (int i = x; i; i -= lowbit(i)) res += tr[i];return res;
}int main() {scanf("%d", &n);for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);for (int i = 1; i <= n; ++i) {int y = a[i];Greater[i] = sum(n) - sum(y);lower[i] = sum(y - 1);add(y, 1);}memset(tr, 0, sizeof tr);LL res1 = 0, res2 = 0;for (int i = n; i; --i) {int y = a[i];res1 += Greater[i] * (LL)(sum(n) - sum(y));res2 += lower[i] * (LL)(sum(y - 1));add(y, 1);}printf("%lld %lld\n", res1, res2);return 0;
}

题目2：241一个简单的整数问题

C++代码如下，

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef long long LL;const int N = 100010;int n, m;
int a[N];
LL c[N];int lowbit(int x) {return x & -x;
}void add(int x, int k) {for (int i = x; i <= n; i += lowbit(i)) c[i] += k;
}LL getsum(int x) {LL res = 0;for (int i = x; i >= 1; i -= lowbit(i)) res += c[i];return res;
}int main() {cin >> n >> m;for (int i = 1; i <= n; ++i) cin >> a[i];for (int i = 1; i <= n; ++i) add(i, a[i] - a[i-1]);for (int i = 0; i < m; ++i) {string op;cin >> op;if (op == "C") {int l, r, d;cin >> l >> r >> d;add(l, d);add(r + 1, -d);} else {int x;cin >> x;cout << getsum(x) << endl;}}return 0;
}

题目3：243一个简单的整数问题2

C++代码如下，

//MYANS
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef long long LL;const int N = 100010;
LL a[N];
LL c1[N], c2[N];
int n, m;int lowbit(int x) {return x & -x;
}void add(LL c[], int x, LL k) {for (int i = x; i <= n; i += lowbit(i)) {c[i] += k;}return;
}LL getsum(LL c[], int x) {LL res = 0;for (int i = x; i >= 1; i -= lowbit(i)) {res += c[i];}return res;
}LL get_query(int x) {return getsum(c1, x) * (x + 1) - getsum(c2, x);
}int main() {cin >> n >> m;for (int i = 1; i <= n; ++i) {cin >> a[i];}for (int i = 1; i <= n; ++i) {int t = a[i] - a[i-1];add(c1, i, t);add(c2, i, (LL)t * i);}while (m--) {string op;cin >> op;if (op == "Q") {int l, r;cin >> l >> r;cout << (LL)get_query(r) - get_query(l - 1) << endl;} else {int l, r, d;cin >> l >> r >> d;add(c1, l, d), add(c1, r + 1, -d);add(c2, l, l * d), add(c2, r + 1, (r + 1) * -d);}}return 0;
}

题目4：244谜一样的牛

C++代码如下，

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 100010;int n;
int h[N];
int ans[N];
int tr[N];int lowbit(int x) {return x & -x;
}void add(int x, int c) {for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}int sum(int x) {int res = 0;for (int i = x; i >= 1; i -= lowbit(i)) res += tr[i];return res;
}int main() {scanf("%d", &n);for (int i = 2; i <= n; ++i) scanf("%d", &h[i]);for (int i = 1; i <= n; ++i) tr[i] = lowbit(i);for (int i = n; i >= 1; --i) {int k = h[i] + 1;int l = 1, r = n;while (l < r) {int mid = l + r >> 1;if (sum(mid) >= k) r = mid;else l = mid + 1;}ans[i] = r;add(r, -1);}for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);return 0;
}

用平衡树做这道题，超时了，通过了 8/10个数据。C++代码如下，

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>using namespace std;const int N = 100010;
int a[N];
int res[N];
set<int> s;
int n;int main() {cin >> n;for (int i = 2; i <= n; ++i) {cin >> a[i];}   for (int i = 1; i <= n; ++i) s.insert(i);for (int i = n; i >= 1; --i) {int k = a[i];//平衡树中第k小的数auto it = s.begin();advance(it, k);res[i] = *it;s.erase(it);}for (int i = 1; i <= n; ++i) cout << res[i] << endl;return 0;
}