数据结构-树状数组专题（1）

一、前言

树状数组可以解决部分区间修改和区间查询的问题，相比于线段树，代码更加简单易懂

二、我的模板

搬运jiangly鸽鸽的模板，特别注意这个模板中所有涉及区间的都是左闭右开区间，且vector的有效下标都从0开始

template <typename T>
struct Fenwick {int n;std::vector<T> a;Fenwick(int n_ = 0) {init(n_);}void init(int n_) {n = n_;a.assign(n, T{});}void add(int x, const T &v) {for (int i = x + 1; i <= n; i += i & -i) {a[i - 1] = a[i - 1] + v;}}T sum(int x) {T ans{};for (int i = x; i > 0; i -= i & -i) {ans = ans + a[i - 1];}return ans;}T rangeSum(int l, int r) {return sum(r) - sum(l);}int select(const T &k) {int x = 0;T cur{};for (int i = 1 << std::__lg(n); i; i /= 2) {if (x + i <= n && cur + a[x + i - 1] <= k) {x += i;cur = cur + a[x - 1];}}return x;}
};

三、树状数组简介

在单点修改和区间查询（单点查询）中，暴力的算法时间复杂度会非常的高，如果想使用前缀和减少时间复杂度，但是我们发现由于频繁地单点修改，导致无法高效地维护前缀和数组，因此衍生出了我们的这个树状数组的高级数据结构。如下图：

观察图，易发现：
C1=A1

C2=A1+A2

C3=A3

C4=A1+A2+A3+A4

C5=A5

C6=A5+A6

C7=A7

C8=A1+A2+A3+A4+A5+A6+A7+A8

于是我们引入lowbit的概念，就是一个数的二进制表示的最低位1表示的数值，例如6的二进制为110,因此10转换成十进制的值即为2，所以6的lowbit是2

关于计算lowbit，有很多方法，可以通过循环找按位右移去找，也可以用x-(x&(x-1))来计算lowbit，还可以用x&(-x)来计算lowbit（最常用也最简洁），至于原理则跟二进制有关，感兴趣的可以自行去了解

树状数组的性质

单点更新操作

如果要更新某个点，那么从这个点开始，下标一直加上当前的lowbit，直到大于最大长度n结束，都需要同时更新它们的值

查询前缀和

如果要查询前k个数的前缀和，那么前缀和的值就等于从k开始一直减去当前lowbit直到k等于0（k取不到0）结束的所有树状数组的值之和

实现区间查询

只需要实现两个前缀和的查询然后相减即可

假如要查询[l,r]这个区间，那么要求出pre[r]的值和pre[l-1]的值，pre表示前缀和

其中单点查询是区间查询的子情况，只不过此时的l等于r而已

后续的专题（2）还有区间修改+单点查询和区间修改+区间查询的高级应用（结合差分）

具体树状数组的细节可以自行翻阅资料，这里就不再展开讲

四、专题训练

4.1 星码StarryCoding P40 【模板】树状数组（单点修改）

思路

树状数组的初始化操作实际上也是一个单点修改的操作，这是个模板题，没什么好说的，直接看代码吧

我的代码

注意可能爆int，因此要开long long，还有要注意下标！！！

//Code Here.
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 2e5+5;template <typename T>
struct Fenwick {int n;std::vector<T> a;Fenwick(int n_ = 0) {init(n_);}void init(int n_) {n = n_;a.assign(n, T{});}void add(int x, const T &v) {for (int i = x + 1; i <= n; i += i & -i) {a[i - 1] = a[i - 1] + v;}}T sum(int x) {T ans{};for (int i = x; i > 0; i -= i & -i) {ans = ans + a[i - 1];}return ans;}T rangeSum(int l, int r) {return sum(r) - sum(l);}int select(const T &k) {int x = 0;T cur{};for (int i = 1 << std::__lg(n); i; i /= 2) {if (x + i <= n && cur + a[x + i - 1] <= k) {x += i;cur = cur + a[x - 1];}}return x;}
};int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int n,q;std::cin >> n >> q;std::vector<i64> a(N,0);for(int i = 1;i <= n;++i) {std::cin >> a[i];}Fenwick<i64> fenwick(N);for(int i = 1;i <= n;++i) {fenwick.add(i-1,a[i]);}while(q--) {int op,l,r,k,v;std::cin >> op;if(op==1) {std::cin >> k >> v;fenwick.add(k-1,v);}else {std::cin >> l >> r;std::cout << fenwick.sum(r)-fenwick.sum(l-1) << '\n';}}return 0;
}

4.2 星码StarryCoding P31 求逆序对个数

思路

提示很明显了，用归并排序或者树状数组都能写，用树状数组写的时候要注意，由于1<=ai<=1e9，因此不能直接开树状数组，会爆栈，所以需要先对a数组做离散化，再开一个树状数组，数组大小为离散化后的数组大小，数组存放的内容是当前下标对应的离散化数组中的值出现的次数（听着有一点绕，可以看下面的代码辅助理解），然后i从1到n遍历，找当前比a[i]大的值（当前比a[i]大的值全都存储在当前树状数组下标的后面，因此可以用区间查询直接算）有多少个，答案就加上多少，然后修改当前的值加一，最后累加得到的答案输出即可

我的代码1

树状数组实现

#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 2e5+5;template <typename T>
struct Fenwick {int n;std::vector<T> a;Fenwick(int n_ = 0) {init(n_);}void init(int n_) {n = n_;a.assign(n, T{});}void add(int x, const T &v) {for (int i = x + 1; i <= n; i += i & -i) {a[i - 1] = a[i - 1] + v;}}T sum(int x) {T ans{};for (int i = x; i > 0; i -= i & -i) {ans = ans + a[i - 1];}return ans;}T rangeSum(int l, int r) {return sum(r) - sum(l);}int select(const T &k) {int x = 0;T cur{};for (int i = 1 << std::__lg(n); i; i /= 2) {if (x + i <= n && cur + a[x + i - 1] <= k) {x += i;cur = cur + a[x - 1];}}return x;}
};int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int n,q;std::cin >> n;std::vector<int> a(N,0),v;//v是离散化数组for(int i = 1;i<=n;++i) {std::cin >> a[i];v.emplace_back(a[i]);}v.emplace_back(0);//放一个0是为了排序后的有效下标从1开始//排序去重std::sort(v.begin(),v.end());v.erase(std::unique(v.begin(),v.end()),v.end());Fenwick<int> fenwick(N);i64 ans = 0;for(int i = 1;i<=n;++i) {int idx = std::lower_bound(v.begin(),v.end(),a[i])-v.begin();ans+=fenwick.sum(v.size()-1)-fenwick.sum(idx);fenwick.add(idx-1,1);}std::cout << ans << '\n';return 0;
}

我的代码2

归并排序实现

#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 2e5+5;i64 ans = 0;
std::vector<int> v(N,0);
std::vector<int> tmp(N,0);using MERGE_SORT = std::function<void(std::vector<int> &,int,int)>;
MERGE_SORT mergeSort = [](std::vector<int> &v,int l,int r)->void {if(l>=r) return;int mid = l+r>>1;mergeSort(v,l,mid);mergeSort(v,mid+1,r);int k = 0,i = l,j = mid+1;while(i<=mid&&j<=r) {if(v[i]<=v[j]) tmp[k++] = v[i++];else tmp[k++] = v[j++],ans+=mid-i+1;}while(i<=mid) tmp[k++] = v[i++];while(j<=r) tmp[k++] = v[j++];for(int i = l,j = 0;i<=r;i++,j++) v[i] = tmp[j];
};int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int n;std::cin >> n;for(int i = 1;i<=n;i++) {std::cin >> v[i];}mergeSort(v,1,n);std::cout << ans << '\n';return 0;
}