[原创] 树状数组的基本讲解

Powered by hjfzzm

Eromanga_Sensei——Izumi Sagiri

• 今天在看线段树的时候猛然间想起来树状数组还没有学，于是乎今天一上午时间补了一下树状数组的坑，其实树状数组只能做部分线段树的题，基本操作同线段树的区间和、单点更新差不多，但是非常好写，查询和修改时间复杂度均为O(log n)。下面简单讲一下。

---

树状数组

• 令这棵树的结点编号为C1，C2，......，Cn。令每个结点的值为这棵树的值的总和，那么容易发现：
  C1 = A1
  C2 = A1 + A2
  C3 = A3
  C4 = A1 + A2 + A3 + A4
  有一个有趣的性质：
  设结点编号为x，那么该结点区间为2^k（其中k为x二进制末尾0的个数）个元素。因为这个区间最后一个元素必为Ax

---

• 计算这个2^k，也就是最低位的1，可以这样写：

int lowbit(int x) {
    return x & (x ^ (x – 1));
}
//或者
int lowbit(int x) {
    return x & -x;
}

---

• 当想要查询一个sum（1-n）时，可以根据以下算法：

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

• 想要修改某点处的值的时候：

int change(int x) {
     for (; x <= maxn; x += x & (-x))
         t[x]++;
}

---

• 完整代码

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100100;
int C[MAX_N];
int n;
int lowbit(int x) {
    return x & (-x);
}
int getsum(int x) {
    int res = 0;
    for(; x; x -= lowbit(x)) {
        res += C[x];
    }
    return res;
}
void change(int x, int c) {
    for(; x <= MAX_N; x += x & (-x)) {
        C[x] += c;
    }
}
int main() {
    cin >> n;
    memset(C, 0, sizeof(C));
    for(int i = 1; i <= n; i++) {
        int d;
        cin >> d;
        change(i, d);
    }
    for(int i = 1; i <= n; i++) {
        cout << getsum(i) << " ";
    }
    return 0;
}

---

• 附加一道想了好久的树状数组的题，明明是线段树的题......这个看懂了基本上树状数组的基本运用就都会了！
• n个木桩排成一排，从左到右依次编号为1，2，3......n。每次给定两个整数a，b，表示从木桩a 到木桩b 涂一次颜色。n次操作后输出第i 个木桩被涂了几次。

输入：
3
1 1
1 2
1 3
输出：
3 2 1

---

• 其实用线段树是特别好做的，区间加一然后直接输出各点的值就行，但是我们学习了树状数组就要用他来解决一次问题。
• 我们知道getsum(x)是计算1-x项和的函数，那么我们联想到前缀和，将起始位置的值标记为1，终止位置的下一位标记为-1，那么题中的样例可以解释为：
  (第四位为虚拟的，用于演示)
  1-1 ：1 -1 0 -1
  1-2 ：2 -1 -1 -1
  1-3 ：3 -1 -1 -1
  那么求1-1，1-2，1-3的和我们就会发现：3 2 1，就为答案。（请读者在这里多思考一会，这里明白了基本上树状数组就明白了）
• 附上完整代码

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100100;
int C[MAX_N];
int n;
int lowbit(int x) {
    return x & (-x);
}
int getsum(int x) {
    int res = 0;
    for(; x; x -= lowbit(x)) {
        res += C[x];
    }
    return res;
}
void change(int x, int c) {
    for(; x <= MAX_N; x += x & (-x)) {
        C[x] += c;
    }
}
int main() {
    cin >> n;
    memset(C, 0, sizeof(C));
    for(int i = 1; i <= n; i++) {
        int p, q;
        cin >> p >> q;
        change(p, 1);
        change(q + 1, -1);
    }
    for(int i = 1; i < n; i++) {
        cout << getsum(i) << " ";
    }
    cout << getsum(n) << endl;
    return 0;
}