笔记 – 树状数组

之前是不是从来没发过数据结构的笔记之类的？那是因为我数据结构太菜了，这几天狂刷数据结构题！

模板 – 树状数组1

支持单点修改，并查询区间和的问题。

最经典的树状数组模板题，这里讲解一下如何操作。

树状数组其实维护的是前缀和，而两个前缀和相减就是区间和。

lowbit

求出该数最后一个1的位置。式子是 x \And -x。

线段树有一个底层，这层的数据是原始的，那么我们要按照二进制统计维护这个前缀和，将 x | 1 = 1 的和 x | 1 = 0 合并到树的第二层，大小为 sum ，那么以此类推，不断维护二进制个数的和，最后就可以以 \mathcal{O}(log_n)的复杂度求出单点的前缀和值。

有了lowbit之后，就可以逐次加上lowbit，优化空间，具体如何使用，体会一下下面的数据。

>>> 4 & -4
>>> 4
>>> 5 & -5
>>> 1
>>> 6 & -6
>>> 2
>>> 8 & -8
>>> 8

发现了没有，不管是从小往大，还是从大往小，通过lowbit处理的数据始终都是将数据靠近\texttt 2的幂次。

模板代码

#include<bits/stdc++.h>
//树状数组 模板1
using namespace std;
typedef long long ll;
const int N = 5e5+10;
int tree[N];
int lowbit(int x){return (x & -x);}
void update(int x, int d) {while(x < N) {tree[x] += d; x += lowbit(x);}}
int sum(int x) {int ans = 0; while(x > 0) {ans += tree[x];x -= lowbit(x);}return ans;}
int n, m;
ll a[N];
int main()
{
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i++) {scanf("%lld", &a[i]); update(i, a[i]);}
  int q, x, y;
  for(int i = 1; i <= m; i++) {
    scanf("%d%d%d", &q, &x, &y);
    if(q == 1) update(x, y);
    else printf("%d\n", sum(y) - sum(x - 1));
  }
  return 0;
}

模板 – 树状数组2

同模板1，求区间的话，其实将单个的值改成差分，这样只要修改区间的左右端点，就可以区间修改。最后要求某一个数的值，由于前缀和是差分的逆运算，所以值在这里就是前缀和，直接询问即可。

Partial Code

  for(int i = 1; i <= n; i++) {
    update(i, a[i] - a[i - 1]);
  }
  int q, x, y;
  ll k;
  while(m--){
    scanf("%d", &q);
    if(q == 1) {
      scanf("%d%d%lld", &x, &y, &k);
      update(x, k);
      update(y + 1, -k);
    }
    else {
      scanf("%d", &x);
      printf("%lld\n", query(x));
    }
  }

例题 – 逆序对

树状数组求逆序对，个人认为会有更多的应用，但是我没遇到过。

首先要离散化，因为树状数组开不下。树状数组维护的是前缀和，那么我们可以求出当前这个数的前面有多少个数，当权值都为\texttt 1的时候。此时，如果我已经将 i 个数放进了树状数组，而 b_i 查询出来小于 i ，那就说明在 i 前面有数被放到 i 后面了，每次加上这些数的个数。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
ll n, b[N], ans, tree[N];
inline int lowbit(int x) { return x & -x; }
inline void update(int x, int d){while (x < N){tree[x] += d;x += lowbit(x);}}
inline int query(int x){int ans = 0;while (x > 0){ans += tree[x];x -= lowbit(x);}return ans;}
struct num{int pos, val;num() {} num(int x, int y) : pos(x), val(y) {}} a[N];
inline bool cmp(num x, num y) {if (x.val == y.val){return x.pos < y.pos;}return x.val < y.val;}
int main()
{
  scanf("%lld", &n);
  for (int i = 1; i <= n; i++){scanf("%lld", &a[i].val);a[i].pos = 1LL * i;}
  sort(a + 1, a + 1 + n, cmp);
  for (int i = 1; i <= n; i++){b[a[i].pos] = i;}
  for (int i = 1; i <= n; i++){update(b[i], 1); ans += i - query(b[i]);}
  printf("%lld\n", ans);
  return 0;
}

区间修改 + 区间查询

$\mathcal{O}(N)$ 建树

有时候树状数组时间被卡了，那么可以考虑线性建树。观察到在建树的时候都是加上自己的lowbit值，而每次都用单点修改会产生很多无用的相加，所以存在线性建树的方法，即递推。

每次只要把自己的lowbit值加上自己即可。

Code

int tr[N]; // 树状数组数据
int a[N];  // 原数组数据
int n;     // 数列长度
int lowbit(int x) { return x & -x; }
// 建树
void build(){
  for (int i = 1; i <= n; i++){
    tr[i] += a[i];
    int fa = i + lowbit(i); // 获得父节点下标
    if (fa <= n)            // 判断父节点是否超出数列范围
      tr[fa] += tr[i];
  }
}

进阶

准备过渡到二维树状数组