树状数组

树状数组 (Binary Indexed Tree / Fenwick Tree)

树状数组是一种用于高效处理前缀和查询和单点修改的数据结构，时间复杂度为 O(log n)。

核心思想

树状数组利用二进制的性质，通过 lowbit 函数来管理区间。每个位置 i 管理的区间长度为 lowbit(i)。

lowbit 函数

int lowbit(int x) {
    return x & (-x);  // 获取 x 的二进制表示中最低位的 1
}

基本操作

初始化

class BIT {
private:
    vector<int> tree;
    int n;
 
public:
    BIT(int size) : n(size), tree(size + 1, 0) {}
 
    // 从数组构造树状数组
    BIT(vector<int>& arr) : n(arr.size()), tree(arr.size() + 1, 0) {
        for (int i = 0; i < arr.size(); i++) {
            update(i + 1, arr[i]);
        }
    }
};

单点修改 (update)

将位置 i 的值增加 delta

void update(int i, int delta) {
    for (; i <= n; i += lowbit(i)) {
        tree[i] += delta;
    }
}

前缀和查询 (query)

查询 [1, i] 的前缀和

int query(int i) {
    int sum = 0;
    for (; i > 0; i -= lowbit(i)) {
        sum += tree[i];
    }
    return sum;
}

区间查询

查询 [l, r] 的区间和

int rangeQuery(int l, int r) {
    return query(r) - query(l - 1);
}

完整代码模板

class BIT {
private:
    vector<int> tree;
    int n;
 
    int lowbit(int x) {
        return x & (-x);
    }
 
public:
    BIT(int size) : n(size), tree(size + 1, 0) {}
 
    // 单点修改：将位置 i 的值增加 delta
    void update(int i, int delta) {
        for (; i <= n; i += lowbit(i)) {
            tree[i] += delta;
        }
    }
 
    // 前缀和查询：查询 [1, i] 的和
    int query(int i) {
        int sum = 0;
        for (; i > 0; i -= lowbit(i)) {
            sum += tree[i];
        }
        return sum;
    }
 
    // 区间查询：查询 [l, r] 的和
    int rangeQuery(int l, int r) {
        return query(r) - query(l - 1);
    }
 
    // 单点查询：查询位置 i 的值
    int pointQuery(int i) {
        return rangeQuery(i, i);
    }
};

高级应用

差分数组 + 树状数组（区间修改，单点查询）

class RangeUpdateBIT {
private:
    BIT diff;  // 差分数组的树状数组
 
public:
    RangeUpdateBIT(int n) : diff(n) {}
 
    // 区间修改：将 [l, r] 的值都增加 delta
    void rangeUpdate(int l, int r, int delta) {
        diff.update(l, delta);
        diff.update(r + 1, -delta);
    }
 
    // 单点查询：查询位置 i 的值
    int pointQuery(int i) {
        return diff.query(i);
    }
};

二维树状数组

class BIT2D {
private:
    vector<vector<int>> tree;
    int n, m;
 
    int lowbit(int x) { return x & (-x); }
 
public:
    BIT2D(int rows, int cols) : n(rows), m(cols), tree(rows + 1, vector<int>(cols + 1, 0)) {}
 
    void update(int x, int y, int delta) {
        for (int i = x; i <= n; i += lowbit(i)) {
            for (int j = y; j <= m; j += lowbit(j)) {
                tree[i][j] += delta;
            }
        }
    }
 
    int query(int x, int y) {
        int sum = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            for (int j = y; j > 0; j -= lowbit(j)) {
                sum += tree[i][j];
            }
        }
        return sum;
    }
 
    int rangeQuery(int x1, int y1, int x2, int y2) {
        return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
    }
};

使用场景

1. 动态前缀和：频繁的单点修改和前缀和查询
2. 逆序对统计：利用树状数组统计逆序对个数
3. 离散化 + 树状数组：处理大范围但稀疏的数据
4. 差分数组优化：区间修改转化为单点修改

时间复杂度

• 单点修改：O(log n)
• 前缀和查询：O(log n)
• 区间查询：O(log n)
• 空间复杂度：O(n)

注意事项

1. 树状数组的下标从 1 开始，不是从 0 开始
2. lowbit(x) 的原理：x & (-x) 可以提取 x 的最低位 1
3. 树状数组只能处理可逆的操作（如加法、异或），不能处理最值操作