树状数组详解（C语言实现高效区间查询与单点更新）

核心思想：lowbit 函数

树状数组的关键在于 lowbit(x) 函数，它返回 x 的二进制表示中最低位的 1 所对应的值。

例如：

• lowbit(6) = lowbit(110₂) = 10₂ = 2
• lowbit(8) = lowbit(1000₂) = 1000₂ = 8

在 C 语言中，lowbit(x) 可以这样实现：

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

C语言实现树状数组

下面我们用 C 语言完整实现一个支持单点更新和前缀和查询的树状数组。

#include <stdio.h>#include <string.h>#define MAXN 100010  // 根据实际需求调整大小int tree[MAXN];  // 树状数组，下标从1开始int n;           // 原数组长度// 返回 x 的 lowbitint lowbit(int x) {    return x & (-x);}// 在位置 i 增加 valvoid update(int i, int val) {    while (i <= n) {        tree[i] += val;        i += lowbit(i);    }}// 查询前缀和 [1, i]int query(int i) {    int sum = 0;    while (i > 0) {        sum += tree[i];        i -= lowbit(i);    }    return sum;}// 初始化树状数组（假设原数组为 arr[1..n]）void init(int arr[]) {    memset(tree, 0, sizeof(tree));    for (int i = 1; i <= n; i++) {        update(i, arr[i]);    }}// 示例主函数int main() {    int arr[] = {0, 1, 3, 5, 7, 9}; // arr[0] 不使用，arr[1..5] 是原数组    n = 5;        init(arr);        printf("前缀和 [1,3]: %d\n", query(3)); // 输出 1+3+5=9        update(2, 2); // 将位置2增加2（原值3 → 5）    printf("更新后前缀和 [1,3]: %d\n", query(3)); // 输出 1+5+5=11        return 0;}

如何支持区间查询？

虽然树状数组直接支持的是前缀和，但我们可以通过差分技巧实现任意区间 [L, R] 的和：

区间和 [L, R] = query(R) - query(L - 1)

这就是为什么树状数组在处理区间查询问题时如此高效。

总结

通过本教程，你已经掌握了树状数组的基本原理和C语言实现方法。它是一种经典的数据结构，在处理动态前缀和、逆序对、区间更新等问题时非常有用。

记住三个关键词：树状数组、C语言实现、数据结构、区间查询。多加练习，你就能在算法题中灵活运用它！

动手试试吧！修改上面的代码，解决你的第一个树状数组问题。