树状数组.md

树状数组

也叫Fenwick树、二叉索引树(Binary Indexed Tree)

区间求和可以使用前缀和去解，时间复杂度O(1)

但是如果元素可变呢？

树状数组适用于 带更新操作 的 区间和查询

结构

代码实现

单点修改，区间查询

基础版本

由A数组建立C数组

int n = A.size();
vector<int> C(n+1, 0);
for (int i = 1; i<=n; i++) {
    add(i, A[i-1]);
}

单点修改

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

区间查询[1,x],位置0为空

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

• 单点修改：add(x, k);
• 区间查询：ask(r) - ask(l - 1);

完整版代码

class Solution {
public:
    vector<int> t;
    int n;

    void build(vector<int> &nums) { // 建树
        n = nums.size();
        t = vector<int>(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            add(i, nums[i - 1]);
        }
    }

    void add(int x, int k) { // 修改某个点
        for (; x <= n; x += x & -x) t[x] += k;
    }

    int ask(int x) { // 查询区间[0,x]
        int ans = 0;
        for (; x>0; x -= x & -x) ans += t[x];
        return ans;
    }
};

树状数组时间复杂度

• 预处理：O(nlog n)
• 更新和查询：O(log n)

区间修改，单点查询

使用差分，维护差分数组d[i] = a[i] - a[i - 1]。 区间更新变成了[l, r] 两端l和r的更新，点查询也就变成了[1, x]的区间更新。

区间修改，区间查询

使用差分，维护差分数组d1[i] = a[i] - a[i - 1] 和 d2[i] = i * (d2[i] - d2[i - 1])。 区间更新的方式和2相同，区间查询是(r + 1) * query(d1, r) - query(d2, r)。通过差分推一推就能得到。

当遇到单点更新时，树状数组往往比线段树更实用

树状数组和线段树比较

• 树状数组功能比线段树少，实现简单，常数小
• 树状数组通常只能用于区间求和
• 线段树能够应用于更多场景，包括：处理区间最大值/最小值等一系列问题
• 线段树实现较复杂，代码长一些

练习题

• LeetCode 307. Range Sum Query - Mutable (medium)

• LeetCode 315. Count of Smaller Numbers After Self (hard)

• LeetCode 493. Reverse Pairs (hard)

• 面试题 10.10. 数字流的秩

拓展

• poj2352 二维偏序；bzoj1452；bzoj1878；bzoj2743；cf755d