树状数组-从入门到拓展
树状数组入门
期间如有问题，欢迎评论区讨论
树状数组是一个可以在O(log2n)的时间复杂度下实现修改和查询的数据结构，因此对于我们在竞赛中起着重要作用
为了能够直观的认识这个时间复杂的意义，我们看下面这个问题
给定长度为n的序列
如果要求我们求出下标区间l-r内数的总和，我们可能会想到直接两个前缀和想减即可
如果我要求把第k个数修改一下，那我们直接修改即可
但是，重点来了，如果我给出m个询问，一共分为两种询问
第一种是需要你对第k个数进行修改
第二种是需要你对当前区间l-r求和，那么，还可以直接算吗？
很显然是不行的，例如我有八个数，我要求2-7之间的区间和，我可以sum[7] - sum[1]，如果我下一步是让你第二个数的值加上x，那么后面的这些前缀和就都需要重新算一边，当我们询问次数高达十的五次方次的时候，显示这种暴力的方法是行不通的
好，带着问题我们开始接触树状数组，首先看一下树状数组
假设我们给出八个数(a[1]、a[2]、....a[8])、那么我们定义树状数组tr
tr[1] = a[1];
tr[2] = a[1] + a[2];
tr[3] = a[3];
tr[4] = a[1] + a[2] + a[3] + a[4];
tr[5] = a[5];
tr[6] = a[5] + a[6];
tr[7] = a[7];
tr[8] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8];
我们使奇数项直接等于我们的原数组，偶数项则是一种和的形式，为了方便理解，下面放上树状数组的一个图形
空白方格不需要管，我们只需要知道，箭头代表我当前方格管理的方格有哪些，例如tr[6]就可以管理a[5] + a[6]
为什么像这样定义呢
当我们需要求出前六项的前缀和的时候，我们想一下，我们只需要tr[6] + tr[4]就可以得到了
当我们需要求出前七项的前缀和的时候，我们只需要tr[7] + tr[6] + tr[4]即可
再者我们考虑修改，假设我需要修改a[2]，其实我们发现，包含a[2]的只有tr[2]、tr[4]、tr[8]这三项
这样我们在边修改边查询的时候，时间复杂度就会降低很多
那么现在我们考虑，这6应该跟4、6关联起来了呢，我们看一下4、6的二进制
6 ：110
4： 100
再看一下前七项前缀和需要用到的7、6、4的
7 ： 111
6 ： 110
4 ： 100
规律就是，每次将二进制中最低位的1减去，直到减完即可
对于修改，我们考虑2和2、4、8的关系
2 ： 10
4 ： 100
8 ： 1000
再考虑包括3的有哪些，3、4、8
3 ： 11
4 ： 100
8 ： 1000
规律就是每次加上二进制中最低位的1，直到超过n
二进制最低位的1也有响应的算法，我们称之为lowbit函数
int lowbit(int x)// 返回x的最低位1
{
return x & -x;
}
这里是利用了负数在计算机内存储形式为补码的特点，感兴趣的可以自己计算一下
单点修改、区间查询
了解了树状数组的内容，和lowbit函数，接下来就是如何实现单点修改和区间查询了
对于单点修改，我们上面提到过，从该点开始，每次加上lowbit，直到最大
这样我们就把可以管理到我们当前数的tr数组给初始化完成了
例如a[2] = 2;那么我就需要把tr[2]、tr[4]、tr[8]都加上这个a[2]，因为他们都可以管理到a[2]
// 单点修改
void update(int x, int c) // a[x] = c;
{
for (int i = x;i <= n; i += lowbit(i)) tr[i] += c;// 如果你可以管理到我，那么你就加上我的值
}
代码很短，多琢磨琢磨就清楚了
考虑前x个数的和，根据我们上面分析的，每次减去最低位的1即可
例如我要求前七个数的和，就是res += tr[7] + tr[6] + tr[4];
// 区间查询
int getsum(int x) // 返回前x个数的和
{
int res = 0;// 前缀和计算结果，用于返回
for (int i = x;i > 0; i -= lowbit(i)) res += tr[i];
return res;
}
下面推荐一道LibreOJ上的例题，推荐这个OJ是因为在这上面提交后是可以看到任何一个测试点的，方便调试
AC代码如下
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int a[N];// 原数组
ll tr[N];// 树状数组
int n, m;
int lowbit(int x)// lowbit函数
{
return x & -x;
}
void update(int x, int c) // a[x] = c
{
for (int i = x;i <= n; i += lowbit(i)) tr[i] += c;
}
ll getsum(int x) // 返回前x个数的和
{
ll res = 0;
for (int i = x;i > 0; i -= lowbit(i)) res += tr[i];
return res;
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// freopen("in.in", "r", stdin);freopen("out.out", "w", stdout);
cin >> n >> m;
for (int i = 1;i <= n;i ++) {
cin >> a[i];
update(i, a[i]);// 初始化tr数组
}
for (int i = 1;i <= m;i ++) {
int id, l, r;
cin >> id >> l >> r;
if (id == 1) {// 修改
update(l, r);// 在l的位置上加r，并更新后面可以管理到他的
}else {// 查询
ll ans = getsum(r) - getsum(l - 1);// 区间和
cout << ans << endl;
}
}
return 0;
}
区间修改、区间查询
说明：线段树挂懒标记可更简单的解决，如果实在不想看树状数组的，可以跳过这里
既然单独提出来了，那么一定是有特点的，不能简简单单考虑，我存的时候存差分不久可以了吗
仔细想想，如果存的时候存的是差分数组，那么你只能进行简单的单点查询，为了能够实现区间查询，我们就要好好考虑一下了
首先对于一个区间和a[1]+a[2]+...+a[n]
定义c为差分数组，那么我们可以得到a[1]+a[2]+...+a[n] = (c[1]) + (c[1]+c[2]) + ... + (c[1]+c[2]+...+c[n])
我们进一步将公式转换= n*c[1] + (n-1)*c[2] +... +c[n]
最终我们得到求和公式= n * (c[1]+c[2]+...+c[n]) - (0*c[1]+1*c[2]+...+(n-1)*c[n])
接下来就可以开始愉快的敲代码了
我们只需要维护两个树状数组c1、c2，其中c1存我们的差分数组，c2存我们的差分数组*系数
推荐题目依旧是LibreOJ上的模板题
AC代码如下
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int n, q;
ll a[N], c1[N], c2[N];
void update(ll *h, int x, ll y){
while(x <= n){
h[x] += y;
x += x & -x;
}
}
ll getsum(ll *h, int x){
ll res = 0;
while(x){
res += h[x];
x -= x & -x;
}
return res;
}
int getsum(int x)//求差分数组c1的前缀和->修改后的原数组
{
int ans = 0;
while (x)
{
ans += c1[x];
x -= lowbit(x);
}
return ans;
}
int main(int argc, char const *argv[])
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
cin >> n >> q;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
update(c1, i, a[i] - a[i - 1]);// c1存 差分
update(c2, i, (i - 1) * (a[i] - a[i - 1]));// c2存 差分*系数
}
for(int i = 1;i <= q;i++){
ll id, l, r, x;
cin >> id >> l >> r;
if(id == 1){
cin >> x;
update(c1, l, x);
update(c1, r + 1, -x);
update(c2, l, x * (l - 1));
update(c2, r + 1, -x * r);
}else{
ll sum1 = (l - 1) * getsum(c1, l - 1) - getsum(c2, l - 1);// 求和公式
ll sum2 = r * getsum(c1, r) - getsum(c2, r);
cout << sum2 - sum1 << endl;
}
}
// for (int i = 1; i <= n; i++)//修改后的原数列、俗称单点查询qwq
// cout << getsum(i) << ‘ ‘;
return 0;
}
区间最值说明
不再对其进行讲解，自行理解即可，很简洁，最大值最小值思路一样
void update(int x, ll y)
{
while (x <= n)
{
c[x] = max(c[x], y);// 谁可以管理到我，谁就对我取max，看我是否可以作为最大值
x += x & -x;
}
}
ll getsum(int x)
{
ll ans = 0;
while (x)
{
ans = max(ans, c[x]);// 对于每一个我可以管理的到，取max
x -= x & -x;
}
return ans;
}
拓展一：逆序数问题
逆序数问题只做为兴趣，实际情况不一定有递归求的快，下面我也会给出递归版本的求逆序数
逆序数就是当前数前面有几个比他大的数
那么我们用树状数组就可以完美的解决这个问题，因为我们树状数组就可以求出了一个数前面的前缀和，如果我们每个数都贡献1，那么求的就是有几个数比我小，然后剩下的，就是比我大的了，就可以做为贡献加入结果中
当然大部分情况下，数会非常大，所以需要离散化一下
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
struct node
{
int x, y;
} que[N];
int tree[N], dispers[N];
int n, cnt = 0, sum;
bool cmp(node a, node b) { return a.x < b.x; }
void update(int x)
{
while (x <= n)
{
tree[x]++;// 默认贡献为1代表个数
x += x & -x;
}
}
int getsum(int x)
{
int ans = 0;
while (x)
{
ans += tree[x];
x -= x & -x;
}
return ans;
}
int main()
{
// freopen("in.txt", "r", stdin);
while (cin >> n)
{
for (register int i = 1; i <= n; i++)
{
cin >> que[i].x;
que[i].y = i;// 用于离散化
}
sort(que + 1, que + n + 1, cmp);
for (register int i = 1; i <= n; i++)// 离散化
{
cnt++;
// cout << cnt << endl;
dispers[que[i].y] = cnt;
}
for (register int i = 1; i <= cnt; i++)
{
update(dispers[i]);// 默认贡献为1，代表个数
sum += (i - getsum(dispers[i]));// 那么剩余的就是比当前数大的了
}
cout << sum << endl;
}
return 0;
}
递归版本代码
原理也比较简单，在递归排序中，我们知道，是通过一个数一个数往前挪的
那么，对于一个数，你在递归排序中，挪了几次，都加起来，就是这个序列的逆序数了
#include <iostream>
#define INF 0xFFFFF
using namespace std;
long long A[1000000];
long long number;
typedef long long ll;
void Merge(int left, int mid, int right)
{
int len1 = mid - left + 1;
int len2 = right - mid;
int L[len1 + 2], R[len2 + 2];
for (int i = 1; i <= len1; i++)
L[i] = A[left + i - 1];
for (int i = 1; i <= len2; i++)
R[i] = A[mid + i];
L[len1 + 1] = R[len2 + 1] = INF;
int l = 1, r = 1;
for (int i = left; i <= right; i++)
{
if (L[l] <= R[r])
A[i] = L[l++];
else
{
A[i] = R[r++];
number += len1 - l + 1;// 如果需要往前挪，就让逆序数加上你挪了几位
}
}
}
void mergeSort(int left, int right)
{
if (left < right)
{
int mid = (left + right) / 2;
mergeSort(left, mid);
mergeSort(mid + 1, right);
Merge(left, mid, right);
}
}
int main()
{
// freopen("in.txt", "r", stdin);
std::ios::sync_with_stdio(false);
long long n;
while (cin >> n)
{
number = 0;
for (register int i = 1; i <= n; i++)
cin >> A[i];
mergeSort(1, n);
cout << number << endl;
// for(register int i=0;i<n;i++) cout << A[i];
// cout << endl;
}
}
拓展二：上升子序列问题
推荐例题AcWing上的3662. 最大上升子序列和
子序列问题大部分是需要dp来求解的
不过用树状数组也有奇效
通过树状数组的性质，我们知道，对于每个树状数组的含义是管理他前面是数，那么我们就可以不只用来求和，用来求最大值也是可以的
对于本题，首先我们修改一下update和getsum函数
void update(int x, ll y)
{
while (x <= n)
{
c[x] = max(c[x], y);// 谁可以管理到我，谁就对我取max，看我是否可以作为最大值
x += x & -x;
}
}
ll getsum(int x)
{
ll ans = 0;
while (x)
{
ans = max(ans, c[x]);// 对于每一个我可以管理的到，取max
x -= x & -x;
}
return ans;
}
我们定义sum数组表示以第i个数结尾的最大上升子序列和，对于我们的序列，我们一个一个判断
对于当前这个数我们考虑比他小的所有数里面，最大的子序列和，并实时更新树状数组
由于我们n只有十的五次方，但是每个数却可能非常大，所以需要离散化一下
AC代码如下
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <map>
#include <unordered_map>
#define INF 0xFFFFFF
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll n, tot = 0;
ll que[N], disperse[N], sum[N], amxsum[N], c[N];
unordered_map<int, ll> mp;
void update(int x, ll y)
{
while (x <= n)
{
c[x] = max(c[x], y);
x += x & -x;
}
}
ll getsum(int x)
{
ll ans = 0;
while (x)
{
ans = max(ans, c[x]);
x -= x & -x;
}
return ans;
}
int main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> que[i];
memcpy(disperse, que, sizeof que);// disperse数组用于存放原数组来离散化
sort(disperse + 1, disperse + n + 1);
for (int i = 1; i <= n; i++)
if (!mp.count(disperse[i]))
mp[disperse[i]] = ++tot;// 每个数是第几大的数
for (int i = 1; i <= n; i++)// 从头往后遍历
{
// 对于在我前面出现并且比我小的数里面，找子序列和最大的，然后加上我的值
// 由于我是第mp[que[i]]大的数，那么我的子序列和最小也得是mp[que[i]]
sum[i] = max(mp[que[i]], getsum(mp[que[i]] - 1) + que[i]);
update(mp[que[i]], sum[i]);//边记录还要变更新以我为结尾最大的子序列和，方便后面的数进行判断
}
ll ans = 0;
for (int i = 1; i <= n; i++)
ans = max(ans, sum[i]);
cout << ans << endl;
return 0;
}
这里是求的最大上升子序列和问题，相应的还有最长上升子序列问题，只需要将这里代码改一下就行了
for (int i = 1; i <= n; i++)// 从头往后遍历
{
sum[i] = max(1ll, getsum(mp[que[i]] - 1) + 1);
update(mp[que[i]], sum[i]);
// sum[i] = max(mp[que[i]], getsum(mp[que[i]] - 1) + que[i]);
// update(mp[que[i]], sum[i]);
}
如果要求非严格上升的话，也只需要把getsum(mp[que[i]] - 1)修改为getsum(mp[que[i]])即可
拓展三：第k小数
推荐题目AcWing244. 谜一样的牛
思路:二分+树状数组
对于中间某一头牛，我们只知道他前面比他高的，并不清楚他后面有几个
但是，对于最后一头牛，如果他前面有k个比他高的，那么他一定是第k + 1个高的牛
对于倒数第二头牛，如果他前面有k个比他高的，那么他一定是除了最后一头牛以外的，第k + 1个高的牛
图示
对于第5头牛，我已经可以确定，他是第1高的，说明他已经占据了第一个位置，那么看第4头牛
因为他前面有一个比它高的，所以我们从1-n进行二分，看那个数前面有1个还存在的高度，然后我们定位到第4头牛的高度为3
看第3头牛，他前面有两个比它高的，从1-n进行二分，我们定位到5这个高度的前面还有两个存在的高度，所以我们定位到第三头牛高度为5
以此类推
所以我们就可以从后往前遍历，每求出一头牛是第几高，我们就将这个高度删去，然后去判断下一头牛
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int a[N], c[N];
int n;
vector<int> res;
inline int lowbit(int x) {
return x & -x;
}
inline void update(int x, int cc) {
for(int i = x;i <= n;i += lowbit(i)) {
c[i] += cc;
}
}
inline int get(int x) {
int res = 0;
for(int i = x;i;i -= lowbit(i)) {
res += c[i];
}
return res;
}
int main(){
scanf("%d", &n);
for(int i = 2;i <= n;i++) {
scanf("%d", &a[i]);
}
for (int i = 1;i <= n;i ++) {
update(i, 1);// 最开始，每一个高度都存在
}
for(int i = n;i;i--){
int l = 1, r = n;
while(l < r){
int mid = l + r >> 1;
if(get(mid) >= a[i] + 1) r = mid;
else l = mid + 1;
}
update(r, -1);// 这个高度已经有牛了，将其删去
res.push_back(r);
}
for(auto i = res.rbegin();i != res.rend();i++){// 由于是倒着求答案的，所以要倒着输出
printf("%d\n", *i);
}
return 0;
}
拓展四：离散化
推荐题目
HDUTuring Tree
T组数据，给定长度为n的序列，m次询问，每次询问区间内不同数相加的和
为了能从左往右进行枚举询问，以每个区间右端点进行排序
然后遍历序列里的n个数
如果这个数在之前出现过，那么我将之前出现的删去，然后在这个位置加上该数，因为每个数只能贡献一次
然后用while循环询问的右端点，是否有右端点与我们遍历到的带你重合了，如果有，那么这个区间里的数我一定已经初始化好了，然后去求这个区间
能看到这里我就不啰嗦这个右端点合理性了，这是完全正确的
#include <iostream>
#include <cstring>
#include <algorithm>
// #include <bits/stdc++.h>
using namespace std;
#define inf 0x7f7f7f7f
typedef long long ll;
const int N = 3e4 + 10, M = 1e5 + 10, mod = 1331;
struct node {
int l, r, k;
bool operator < (const node &t) const {// 自定义以区间右端点排序
return r < t.r;
}
}q[M];
int a[N], b[N];
ll tr[N], res[M];//res存储第i个区间的答案
int vis[N];// 第i个数最后一次出现的位置
int n, m;
int lowbit(int x)
{
return x & -x;
}
void update(int x, int c) // 位置x加c
{
for (int i = x;i <= n; i += lowbit(i)) tr[i] += c;
}
ll getsum(int x) // 返回前x个数的和
{
ll res = 0;
for (int i = x;i > 0; i -= lowbit(i)) res += tr[i];
return res;
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// freopen("in.in", "r", stdin);freopen("out.out", "w", stdout);
int T;
cin >> T;
while (T --) {
memset(tr, 0, sizeof tr);
memset(vis, 0, sizeof vis);
cin >> n;
for (int i = 1;i <= n;i ++) {
cin >> a[i];
b[i] = a[i];
}
sort(b + 1, b + n + 1);// 排序用于离散化
for (int i = 1;i <= n;i ++) {// 二分函数离散化
a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
}
cin >> m;
for (int i = 1;i <= m;i ++) {
cin >> q[i].l >> q[i].r;
q[i].k = i;
}
sort(q + 1, q + m + 1);
int cnt = 1;
for (int i = 1;i <= n;i ++) {
if (vis[a[i]]) update(vis[a[i]], -b[a[i]]);// 如果你出现过，我先将你前面的贡献删去
update(i, b[a[i]]);// 在当前位置上加上贡献
vis[a[i]] = i;// 记录当前点，用于后面重复了以后进行删除
// 如果右端点与我枚举的位置重合了，那么这个区间里的数我一定已经初始化好了，然后去求这个区间
while (cnt <= m && q[cnt].r == i) {
res[q[cnt].k] = getsum(q[cnt].r) - getsum(q[cnt].l - 1);
cnt ++;
}
}
// cout << m << "---" << endl;
for (int i = 1;i <= m;i ++) {
cout << res[i] << endl;
}
}
return 0;
}