树状数组

树状数组的基本应用：

$O(\log n)$单点修改、区间查询

原理：

设区间$[1,R]$，对区间右端点$R$做二进制拆分，有：

$$R=2^{x_1}+2^{x_2}+\cdots +2^{x_k}$$

假设$x_1\sim x_k$严格单调递减，那么可以把区间$[1,R]$拆分成$\log R$个区间

$$\begin{gathered} [1,2^{x_1}], \\ [2^{x_1}+1,2^{x_1}+2^{x_2}], \\ \cdots , \\ [2^{x_1}+2^{x_2}+\cdots +2^{x_{k-1}}+1,2^{x_1}+2^{x_2}+\cdots +2^{x_k}] \end{gathered}$$

可以发现每个区间的长度就等于每个区间结尾的$\text{lowbit}$，所以可以建立一个数组$tr$，保存区间$[R-\text{lowbit}(R)+1,R]$的和，也就是树状数组。

查询区间和：

对区间$[L,R]$只需要求出${\sum }_{i=1}^R-{\sum }_{i=1}^{L-1}$。

所以目标只要计算区间$[1,i]$的和：设$i$的二进制下的最后一位$1$是第$k$位，那么只需要求出$k-1$个子节点的和加上$tr[i]$，访问每个子节点只需要减去$\text{lowbit}(i)$，一共$\log i$次，所以时间复杂度为$O(\log n)$

代码：

int ask(int x) {
   
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

单点修改

假设令$a_i$增加$c$，考虑只有$tr[i]$及其祖先节点保存$a_i$的值，所以只需要每次加上$\text{lowbit}(i)$，就可以一直修改祖先节点，最多$\log n$次，所以时间复杂度为$O(\log n)$

代码：

void update(int x, int c) {
   
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

树状数组的扩展应用：

$1.$求某个数前面或后面有几个数比它大或小

AcWing 788 逆序对的数量

分析： 令$tr[x]$定义为$x$出现的次数，那么${\sum }_{i=L}^{R}tr[i]$就表示在区间$[L,R]$中出现的数有多少个，那么相当于在$x$的数值范围上建立一个树状数组。所以求逆序对时可以倒序统计$i$之后比$a_i$小的数，每次将$tr[a_i]+1$

代码：

#include <bits/stdc++.h>
#define int long long
#define lowbit(x) x & -x
using namespace std;
const int N = 1e6 + 5;
int n, a[N], tr[N], res;
int ask(int x) {
   
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}
void update(int x, int c) {
   
    for (int i = x; i <= N; i += lowbit(i)) tr[i] += c;
}
signed main() {
   
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = n; i; i --) {
   
        res += ask(a[i] - 1);
        update(a[i], 1);
    }
    cout << res << endl;
}

AcWing 241 楼兰图腾

分析： 与逆序对一样，在取值范围建立树状数组。求比$a_i$小直接用$ask(a_i-1)$，求比$a_i$大的数可以用$ask(n)-ask(a_i)$这一前缀和技巧处理。

代码：

#include <bits/stdc++.h>
#define int long long
#define lowbit(x) x & -x
using namespace std;
const int N = 2e5 + 5;
int n, a[N], tr[N], res1, res2, high[N], low[N];
void update(int x, int c) {
   
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
int ask(int x) {
   
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}
signed main() {
   
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++) {
   
        high[i] = ask(n) - ask(a[i]);
        low[i] = ask(a[i] - 1);
        update(a[i], 1);
    }
    memset(tr, 0, sizeof tr);
    for (int i = n; i; i --) {
   
        res1 += high[i] * (ask(n) - ask(a[i]));
        res2 += low[i] * ask(a[i] - 1);
        update(a[i], 1);
    }
    cout << res1 << " " << res2 << endl;
}

$2.$区间修改，单点查询

AcWing 242 一个简单的整数问题

分析： 可以利用差分的思想，在区间$[L,R]$加上某一个数$c$，那么就是在差分数组$b$上将$b_L+c,b_{R+1}-c$，所以可以用树状数组维护$a_i$的差分。

代码：

#include <bits/stdc++.h>
#define int long long
#define lowbit(x) x & -x
using namespace std;
const int N = 1e5 + 5;
int n, m, a[N], tr[N], l, r, x, d;
char op;
int ask(int x) {
   
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}
void update(int x, int c) {
   
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
signed main() {
   
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++) update(i, a[i] - a[i - 1]);
    while (m --) {
   
        cin >> op;
        if (op == 'Q') {
   
            cin >> x;
            cout << ask(x) << endl;
        } else if (op == 'C') {
   
            cin >> l >> r >> d;
            update(l, d), update(r + 1, -d);
        }
    }
}

$3.$ 区间修改，区间查询

AcWing 243 一个简单的整数问题2

分析： 区间修改可以用差分维护，那么如果查询区间$[1,R]$，就等价于求

$$\sum _{i=1}^R\sum _{j=1}^i{b}_j=\sum _{i=1}^R(R-i+1)\ast b_i=(R+1)\sum _{i=1}^R{b}_i-\sum _{i=1}^{R}i\ast b_i$$

所以只需要再增加一个树状数组维护$i\ast b_i$的前缀和即可。

代码：

#include <bits/stdc++.h>
#define int long long
#define lowbit(x) x & -x
using namespace std;
const int N = 1e5 + 5;
int n, m, a[N], l, r, d, tr1[N], tr2[N];
char op;
void update(int tr[], int x, int c) {
   
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
int ask(int tr[], int x) {
   
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}
int sum(int x) {
   
    return ask(tr1, x) * (x + 1) - ask(tr2, x);
}
signed main() {
   
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++) update(tr2, i, i * (a[i] - a[i - 1])), update(tr1, i, a[i] - a[i - 1]);
    while (m --) {
   
        cin >> op;
        if (op == 'Q') {
   
            cin >> l >> r;
            cout << sum(r) - sum(l - 1) << endl;
        } else if (op == 'C') {
   
            cin >> l >> r >> d;
            update(tr1, l, d), update(tr2, l, d * l);
            update(tr1, r + 1, -d), update(tr2, r + 1, (r + 1) * -d);
        }
    }
}