课外学习地址：https://blog.csdn.net/Antonio915/article/details/142336465

数状数组代码如下：

#include <vector>
using namespace std;

const int MAXN = 100005; // 根据题目需求设置最大值
int n;                  // 数组大小
int tree[MAXN];         // 树状数组

// lowbit 函数：返回 x 的二进制表示中最低位 1 所对应的值
inline int lowbit(int x) {
    return x & (-x);
}

// 单点修改：将原数组第 i 位置增加 x
void add(int i, int x) {
    while (i <= n) {
        tree[i] += x;
        i += lowbit(i);
    }
}

// 前缀和查询：返回原数组前 i 个元素的和（即 [1, i] 区间和）
int query(int i) {
    int res = 0;
    while (i > 0) {
        res += tree[i];
        i -= lowbit(i);
    }
    return res;
}

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

结构体的写法

#include <vector>
#include <cstring>  // 如果需要 memset 初始化

struct BIT {
    int n;
    std::vector<int> tree;

    // 构造函数：初始化大小为 n 的树状数组
    BIT(int size) : n(size) {
        tree.resize(n + 1, 0);  // 下标从 1 开始，所以大小为 n+1
    }

    // lowbit 函数：获取最低位的 1 所代表的数值
    inline int lowbit(int x) {
        return x & (-x);
    }

    // 单点增加：在位置 i 上加上 x
    void add(int i, int x) {
        while (i <= n) {
            tree[i] += x;
            i += lowbit(i);
        }
    }

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

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

    // 可选：批量初始化（传入原始数组）
    void init(const std::vector<int>& arr) {
        for (int i = 0; i < arr.size() && i < n; ++i) {
            add(i + 1, arr[i]);  // 原数组下标从 0 开始，BIT 从 1 开始
        }
    }
};

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com