树状数组(Binary Indexed Tree)完全指南：单点更新、前缀和与逆序对应用

一、基础概念与性质

1.1 什么是树状数组

树状数组（Binary Indexed Tree，简称BIT），也称为Fenwick Tree，是一种用于高效处理前缀和查询和单点更新的数据结构。它由Peter Fenwick于1994年发明。

与线段树相比，树状数组的代码更简洁，常数更小，但功能相对有限。

1.2 核心性质

基于二进制表示：利用数的二进制性质实现高效操作
空间紧凑：只需要n个空间（不像线段树需要4n）
操作简洁：核心操作只有update和query
log级复杂度：单次操作时间复杂度O(log n)

1.3 与线段树对比

特性	树状数组	线段树
代码复杂度	简单	复杂
空间复杂度	O(n)	O(4n)
常数因子	小	大
单点更新	O(log n)	O(log n)
区间查询	O(log n)	O(log n)
区间更新	需要变形	直接支持（懒标记）
功能多样性	有限	强大

1.4 图解原理

索引（二进制）：  1(001)  2(010)  3(011)  4(100)  5(101)  6(110)  7(111)  8(1000)
tree数组：       [1]     [1-2]   [3]     [1-4]   [5]     [5-6]   [7]     [1-8]

lowbit(6)=2 → tree[6] = a[5] + a[6]
lowbit(4)=4 → tree[4] = a[1] + a[2] + a[3] + a[4]

—

二、算法原理与实现

2.1 lowbit操作

lowbit(x)返回x的二进制表示中最低位的1所对应的值：

// 核心操作：lowbit
int lowbit(int x) {
    return x & -x;  // 利用补码性质
}

// 示例：
// lowbit(6) = lowbit(110) = 10(2) = 2
// lowbit(5) = lowbit(101) = 1(1) = 1
// lowbit(8) = lowbit(1000) = 1000(8) = 8

2.2 基础实现（单点更新、前缀和查询）

#include <iostream>
#include <vector>
using namespace std;

class BIT {
private:
    vector<int> tree;
    int n;

public:
    BIT(int size) : n(size) {
        tree.resize(n + 1, 0);  // 下标从1开始
    }

    // 单点更新：在位置idx加上val
    void update(int idx, int val) {
        while (idx <= n) {
            tree[idx] += val;
            idx += lowbit(idx);
        }
    }

    // 查询前缀和：[1, idx]的和
    int query(int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= lowbit(idx);
        }
        return sum;
    }

    // 查询区间和：[l, r]的和
    int range_query(int l, int r) {
        return query(r) - query(l - 1);
    }

private:
    int lowbit(int x) {
        return x & -x;
    }
};

2.3 主函数调用示例

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    BIT bit(n);

    // 初始化
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        bit.update(i, x);
    }

    int m;
    cin >> m;

    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            // 单点更新
            int idx, val;
            cin >> idx >> val;
            bit.update(idx, val);
        } else {
            // 区间查询
            int l, r;
            cin >> l >> r;
            cout << bit.range_query(l, r) << '\n';
        }
    }

    return 0;
}

2.4 不使用类的简洁版本

const int MAXN = 100005;
int tree[MAXN];
int n;

int lowbit(int x) {
    return x & -x;
}

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

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

—

三、经典入门例题

例题1：逆序对计数

题目描述：
给定一个排列，计算其中逆序对的数量。逆序对是指数组中i < j但a > a[j]的对数。

算法思路：

从后往前遍历数组
查询当前元素之前（已处理的）比它小的数的个数
将当前元素加入树状数组

完整代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class BIT {
private:
    vector<int> tree;
    int n;

    int lowbit(int x) {
        return x & -x;
    }

public:
    BIT(int size) : n(size) {
        tree.resize(n + 1, 0);
    }

    void update(int idx, int val) {
        while (idx <= n) {
            tree[idx] += val;
            idx += lowbit(idx);
        }
    }

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

long long countInversions(vector<int>& arr) {
    int n = arr.size();
    
    // 离散化（处理数值很大的情况）
    vector<int> temp = arr;
    sort(temp.begin(), temp.end());
    for (int i = 0; i < n; i++) {
        arr[i] = lower_bound(temp.begin(), temp.end(), arr[i]) - temp.begin() + 1;
    }

    BIT bit(n);
    long long inversions = 0;

    // 从后往前遍历
    for (int i = n - 1; i >= 0; i--) {
        inversions += bit.query(arr[i] - 1);  // 查询比当前元素小的数量
        bit.update(arr[i], 1);
    }

    return inversions;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    cout << countInversions(arr) << endl;

    return 0;
}

例题2：区间更新、单点查询

题目描述：
实现区间加法和单点查询。

算法思路：
利用差分思想：

区间[l, r]加val → update(l, val), update(r+1, -val)
单点查询 → query(idx)

完整代码：

#include <iostream>
#include <vector>
using namespace std;

class BIT {
private:
    vector<int> tree;
    int n;

    int lowbit(int x) {
        return x & -x;
    }

public:
    BIT(int size) : n(size) {
        tree.resize(n + 2, 0);  // 多开一位防止r+1越界
    }

    void update(int idx, int val) {
        while (idx <= n) {
            tree[idx] += val;
            idx += lowbit(idx);
        }
    }

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

    // 区间[l, r]加上val
    void range_update(int l, int r, int val) {
        update(l, val);
        update(r + 1, -val);
    }

    // 单点查询
    int point_query(int idx) {
        return query(idx);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    BIT bit(n);

    // 输入初始数组
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            // 区间更新
            int l, r, val;
            cin >> l >> r >> val;
            bit.range_update(l, r, val);
        } else {
            // 单点查询
            int idx;
            cin >> idx;
            cout << a[idx] + bit.point_query(idx) << '\n';
        }
    }

    return 0;
}

—

四、进阶应用：区间更新、区间查询

4.1 二维树状数组

用于处理二维前缀和问题：

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.resize(n + 1, vector<int>(m + 1, 0));
    }

    // 单点更新
    void update(int x, int y, int val) {
        for (int i = x; i <= n; i += lowbit(i)) {
            for (int j = y; j <= m; j += lowbit(j)) {
                tree[i][j] += val;
            }
        }
    }

    // 查询前缀和(1,1)到(x,y)
    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;
    }

    // 区间查询：(x1,y1)到(x2,y2)
    int range_query(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);
    }
};

// 应用：二维差分
void range_update2D(BIT2D& bit, int x1, int y1, int x2, int y2, int val) {
    bit.update(x1, y1, val);
    bit.update(x1, y2 + 1, -val);
    bit.update(x2 + 1, y1, -val);
    bit.update(x2 + 1, y2 + 1, val);
}

4.2 区间更新、区间查询（一维）

使用两个树状数组实现：

class RangeBIT {
private:
    vector<long long> tree1, tree2;
    int n;

    int lowbit(int x) {
        return x & -x;
    }

    void update(vector<long long>& tree, int idx, long long val) {
        while (idx <= n) {
            tree[idx] += val;
            idx += lowbit(idx);
        }
    }

    long long query(vector<long long>& tree, int idx) {
        long long sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= lowbit(idx);
        }
        return sum;
    }

public:
    RangeBIT(int size) : n(size) {
        tree1.resize(n + 2, 0);
        tree2.resize(n + 2, 0);
    }

    // 区间[l, r]加val
    void range_add(int l, int r, long long val) {
        update(tree1, l, val);
        update(tree1, r + 1, -val);
        update(tree2, l, val * (l - 1));
        update(tree2, r + 1, -val * r);
    }

    // 查询前缀和[1, x]
    long long prefix_sum(int x) {
        return query(tree1, x) * x - query(tree2, x);
    }

    // 区间查询[l, r]
    long long range_sum(int l, int r) {
        return prefix_sum(r) - prefix_sum(l - 1);
    }
};

4.3 完整代码示例

#include <iostream>
#include <vector>
using namespace std;

class RangeBIT {
private:
    vector<long long> tree1, tree2;
    int n;

    int lowbit(int x) {
        return x & -x;
    }

    void update(vector<long long>& tree, int idx, long long val) {
        for (; idx <= n; idx += lowbit(idx)) {
            tree[idx] += val;
        }
    }

    long long query(vector<long long>& tree, int idx) {
        long long res = 0;
        for (; idx > 0; idx -= lowbit(idx)) {
            res += tree[idx];
        }
        return res;
    }

public:
    RangeBIT(int size) : n(size) {
        tree1.resize(n + 2, 0);
        tree2.resize(n + 2, 0);
    }

    void range_add(int l, int r, long long val) {
        update(tree1, l, val);
        update(tree1, r + 1, -val);
        update(tree2, l, val * (l - 1));
        update(tree2, r + 1, -val * r);
    }

    long long prefix_sum(int x) {
        return query(tree1, x) * x - query(tree2, x);
    }

    long long range_sum(int l, int r) {
        return prefix_sum(r) - prefix_sum(l - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    RangeBIT bit(n);

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        bit.range_add(i, i, a[i]);
    }

    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r, val;
            cin >> l >> r >> val;
            bit.range_add(l, r, val);
        } else {
            int l, r;
            cin >> l >> r;
            cout << bit.range_sum(l, r) << '\n';
        }
    }

    return 0;
}

—

五、复杂度分析

操作	时间复杂度	空间复杂度
单点更新	O(log n)	O(n)
前缀和查询	O(log n)	O(n)
区间和查询	O(log n)	O(n)
区间更新（差分）	O(log n)	O(n)
二维单点更新	O(log n log m)	O(nm)

说明：

每次操作最多跳log n次（每次跳lowbit）
树状数组的常数非常小，实际运行效率很高

—

六、更多经典应用

6.1 第K小查询

// 求第k小元素
int findKth(BIT& bit, int n, int k) {
    int idx = 0;
    int mask = 1;
    
    // 从最高位开始试探
    while (mask <= n) mask <<= 1;
    mask >>= 1;
    
    while (mask > 0) {
        int t = idx + mask;
        if (t <= n && bit.query(t) < k) {
            idx = t;
            k -= bit.query(t);
        }
        mask >>= 1;
    }
    
    return idx + 1;
}

6.2 离散化技巧

当数值范围很大但元素个数不多时，需要离散化：

vector<int> discretize(vector<int>& arr) {
    vector<int> temp = arr;
    sort(temp.begin(), temp.end());
    temp.erase(unique(temp.begin(), temp.end()), temp.end());
    
    vector<int> res(arr.size());
    for (int i = 0; i < arr.size(); i++) {
        res[i] = lower_bound(temp.begin(), temp.end(), arr[i]) - temp.begin() + 1;
    }
    return res;
}

—

七、总结与学习建议

7.1 模板总结

核心代码：

int lowbit(int x) { return x & -x; }

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

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

7.2 学习建议

基础阶段：先实现单点更新、前缀和查询，理解lowbit的原理
理解阶段：手写3遍代码，理解update和query的跳转过程
进阶阶段：学习逆序对、差分思想（区间更新、单点查询）
精通阶段：学习区间更新+区间查询、二维树状数组

7.3 常见坑点提醒

下标从1开始：树状数组必须从1开始，不能从0开始
long long：结果可能很大，记得用long long
离散化：数值很大时记得离散化，注意去重
二维数组大小：二维树状数组空间是O(nm)，注意内存限制
差分边界：r+1不要越界，多开空间

7.4 树状数组 vs 线段树选择建议

场景	推荐使用
单点更新、前缀和查询	树状数组
区间加、单点查询	树状数组（差分）
区间加、区间和查询	都可以
区间乘、复杂标记	线段树
求最值	线段树更方便
需要区间分裂合并	线段树

7.5 推荐练习题

难度	题目	来源	知识点
入门	树状数组模板	洛谷P3374	单点加、区间和
入门	逆序对	洛谷P1908	经典应用
中等	区间加、区间和	洛谷P3368	双树状数组
中等	二维树状数组	模板题	二维前缀和
困难	楼兰图腾	洛谷P2345	逆序对变形
困难	MooFest	POJ1990	排序+BIT

树状数组是信息学竞赛中性价比极高的数据结构，虽然功能不如线段树全面，但代码简洁、常数小，是很多题目的首选解法。掌握树状数组，你就能在竞赛中快速优雅地解决大量问题！