【数据结构】树状数组

树状数组

给出一个长度为n的数组，完成以下两个操作

将第x个数加上k

输出区间\([x,y]\)内每个数的和

前缀和

使用前缀和进行询问时，可以通过询问r与l-1处的前缀和并相减获得区间数之和

但进行增加操作时，若想实现在某位置i处增加v，那么该数后面的所有元素都要对应增加v

对于这个问题，朴素算法能做到\(O(n^2)\)的时间复杂度，易TLE

优化思维

单个求区间和会超时，我们可以对数组进行处理：

我们可以把数字两两求和，存到另一个数组中，再进行两两求和，一直到剩一个数字

这样即使要求的数很多，我们也可以利用额外的数组计算答案

如计算前15个数的和，我们只需要计算4个数字即可

但我们可以发现，每层中第偶数个数字是没有用的，因为都可以找到更上一层的代替，去掉以后，剩下的数据恰好为n个，可以装到一个数组中，与原始数组一样长

该数组即为树状数组，每个元素都对应着树的每个节点，而每个节点对应的是原数组的某个区间和

也可以理解为每个元素是以该元素为右边界所管辖的最长区间和中元素个数

求和时只需要找到对应区间，相加即可得到答案

修改某个数据时，也只需要向上找到包含它的区间进行修改即可

lowbit()运算

定义

表示非负整数二进制表示下最低位1及其后面的0构成的数

即实现了提取最右侧1，并让其余位置变为0

e.g. \(lowbit(44)=lowbit((101100)_2)=(100)_2=4\)

求解方法

如44，二进制为101100

首先将该数取反：\(\sim101100=010011\)

然后加一：\(010011+1=010100\)

这时发现除了最低位1与后面的0，其余位上与原数均不同

将这两个数按位与：\(101100 \and 010100=000100\)

故lowbit(n)=n&(~n+1)=n&-n

树状数组实现

我们根据序列建造一棵树，每个节点\(t[x]\) 保存以\(x\)为根的子树中叶节点值之和

将每个\(t[x]\)的x转化为二进制，我们发现每一层末尾0的个数相同，且0的个数与其覆盖长度有关，每层的lowbit()值都相同

故\(t[x]\)节点覆盖长度就是lowbit(x) ，序号为i的序列正好就是长度为lowbit(i)且以i结尾的序列

且\(t[x]\)节点的父节点为\(t[x+lowbit(x)]\)

整棵树的深度为\(\log n +1\)

add()操作

对于add(x,k)操作，若要在整棵树上维护这个值，需要一层一层找到父节点，并按照需要来修改这个节点的值

void add(int x,int k){
    for(;x<=n;x+=x&-x) t[x]+=k;
}

最坏复杂度：\(O(\log n)\)

ask()操作

向坐上找一个节点，只需要将下标-=lowbit(这个节点的下标)

int ask(int x){
    int ans = 0;
    for (; x; x-=x&-x) ans+=t[x];
    return ans;
}

最坏复杂度：\(O(\log n)\)

应用

树状数组是一个动态维护前缀和的工具

单点修改，单点查询

add(x,k);
ans=ask(x)-ask(x-1);

单点修改，区间查询

add(x,k);
ans=ask(r)-ask(l-1);

区间修改，单点查询

由差分可知，原数组第i项可以由差分数组第1项到第i项累加获得

则对于区间修改，只需要在对应l与r+1处进行val的修改即可完成对整个差分数组的修改

引入差分数组b，用树状数组维护b的前缀和，即a数组每个元素的增量

区间修改：\([l,r]+d\) add(l,d); add(r+1,-d)

单点查询：ans = a[x]+ask(x)

add(l,d); add(r+1,-d);
ans=a[x]+ask(x);

区间修改，区间查询

将k项数按差分数组和拆开合并如下

故我们可以维护两棵树，转换为四条add

查询操作按找公式分别计算两棵树

设树状数组\(t_1\)维护b[i]前缀和，\(t_2\)维护i*b[i]前缀和

区间修改：

对\(t_1\)，add1(l,d), add1(r+1,-d)
对\(t_2\)，add2(l,(l-1)*d), add2(r+1,-r*d)

区间查询：ans=(sum[r]+(r+1)*ask1(r)-ask2(r))-(sum[l-1]+l*ask1(l-1)-ask2(l-1))

int t1[maxn],t2[maxn];
void add1(int x,int k){
    for(;x<=n;x+=x&x-x) t1[x]+=k;
}
int ask1(int x){
    int ans = 0;
    for (; x; x-=x&-x) ans+=t1[x];
    return ans;
}
void add2(int x,int k){
    for(;x<=n;x+=x&x-x) t2[x]+=k;
}
int ask2(int x){
    int ans = 0;
    for (; x; x-=x&-x) ans+=t2[x];
    return ans;
}
add1(l,d); add1(r+1,-d); add2(l,(l-1)*d); add2(r+1, -r*d);
ans=(sum[r]+(r+1)*ask1(r)-ask2(r))-(sum[l-1]+l*ask1(l-1)-ask2(l-1))

应用：逆序对

查询符合条件逆序对思路

从右往左遍历，每次将搜到的数计入词频数组++，并查询该位置右侧有多少小于该位置数的数，可以通过对词频数组进行前缀和（求和到该位置-1）获得

由于一直在查询前缀和，可以将词频数组构建树状数组，查询能到到\(O(\log n)\)

由于该题数据范围很大，若直接建立树状数组空间会炸，故需要离散化获得数据间的相对大小

离散化

该树状数组叫做值域树状数组：下标为值，对应值为词频，故下标要支持值域的数据范围

处理：将原数组复制并排序，从左到右遍历，且要将相同值去掉

回到原数组，用二分查找当前数在排序数组中的位置，用位置下标替换当前值

这样操作结束后，数与数之间的相对大小没有变化，故逆序对的数量也不会变化

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> PII;
const int N = 5e5 + 10;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
ll arr[N];
ll sorted[N];
ll tree[N];
ll n;
void add(ll x,ll k){
  for (;x<=n;x+=x&-x)tree[x]+=k;
}
ll ask(ll x){
  ll ans = 0;
  for (;x;x-=x&-x) ans += tree[x];
  return ans;
}
void solve() {
  ll re = 0;
  cin >> n;
  for (int i = 1;i<=n;i++){
    cin >> arr[i];
    sorted[i]=arr[i];
  } 
  sort(sorted+1,sorted+n+1); // 对用于离散化的数组排序
  ll m = 1;
  // 对sorted数组去重，以得到实际参与离散化的范围1-m
  for (int i = 2;i<=n;i++){
    if(sorted[m]!=sorted[i]){
      sorted[++m]=sorted[i];
    }
  }
  // 二分查找
  auto b_sort = [&](ll x){
    ll l = 0, r = m+1, ans = 0;
    while(l+1!=r){
      ll mid = (l+r)/2;
      if (sorted[mid]>=x){
        //ans = mid;
        r=mid;
      } 
      else l = mid;
    }
    return r;
  };
  for (int i = 1;i<=n;i++){
    arr[i]=b_sort(arr[i]); // 二分查找找到对应数在sorted的位置并将值替换为下标，进行离散化
  }
  for (int i = n;i>=1;i--){
    add(arr[i],1); // 词频+1
    re += ask(arr[i]-1); // 寻找小于当前数-1的词频前缀和
  }
  cout <<re << endl;

}
int main()
{
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int tomorin=1;
  //cin >> tomorin;
  while (tomorin--) solve();
  return 0;
}