树状数组（Fenwick Tree）

小橘子🍊

2026-07-31 19:25:17

发布于：福建

13阅读

0回复

0点赞

一、什么是树状数组

树状数组是一种用于高效维护前缀和的数据结构，支持：

单点修改：O(log n)
区间查询：O(log n)

相比于前缀和数组（查询 O(1) 但修改 O(n)），树状数组在需要频繁修改和查询的场景下表现优异。
二、核心原理

树状数组利用二进制拆分的思路，将每个位置管理一段区间。
lowbit 操作

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

作用：lowbit(x) 表示 x 管辖的区间长度。

例如：

lowbit(6) = 2

lowbit(8) = 8

树状数组的存储方式

c[i] 表示原数组 a[i - lowbit(i) + 1] 到 a[i] 的和。
三、基本操作

单点修改

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

前缀查询

int query(int x) {
    int res = 0;
    for(int i = x; i > 0; i -= lowbit(i)) {
        res += c[i];
    }
    return res;
}

区间查询

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

四、经典应用：逆序对

问题：给定数组，求满足 i < j 且 a[i] > a[j] 的数对个数。

思路：从右往左遍历，统计比当前元素小的个数。

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 500005;
int n, a[MAXN], b[MAXN], c[MAXN];

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

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

long long query(int x) {
    long long res = 0;
    for(int i = x; i > 0; i -= lowbit(i)) {
        res += c[i];
    }
    return res;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    int m = unique(b + 1, b + n + 1) - b - 1;
    long long ans = 0;
    for(int i = n; i >= 1; i--) {
        int pos = lower_bound(b + 1, b + m + 1, a[i]) - b;
        ans += query(pos - 1);
        add(pos, 1);
    }
    printf("%lld\n", ans);
    return 0;
}

五、模板总结

lowbit 函数

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

2.单点修改

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

前缀查询

int query(int x) {
    int res = 0;
    for(int i = x; i > 0; i -= lowbit(i)) {
        res += c[i];
    }
    return res;
}

区间查询

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

六、总结

掌握要点：

理解 lowbit 的含义和计算
掌握 add 和 query 的更新/查询路径
能够处理离散化
能够解决逆序对、偏序等经典问题

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论