树状数组:

#include <vector>
#include <stdexcept>

template <typename T>
class FenwickTree {
	private:
		std::vector<T> tree;  // 树状数组的底层存储
		int n;                // 数组的大小
	
		// 获取x的二进制表示中最低位的1所对应的值
		int lowbit(int x) const {
			return x & -x;
		}
	
	public:
		// 构造函数，初始化树状数组
		FenwickTree(int size = 0) : n(size), tree(size + 1, 0) {}
	
		// 构造函数，从已有数组初始化
		FenwickTree(const std::vector<T>& arr) {
			n = arr.size();
			tree.resize(n + 1, 0);
			for (int i = 0; i < n; ++i) {
				update(i + 1, arr[i]);  // 注意树状数组是1-based索引
			}
		}
	
		// 更新操作：在索引index处增加delta（index是1-based）
		void update(int index, T delta) {
			if (index < 1 || index > n) {
				throw std::out_of_range("Index out of range");
			}
			while (index <= n) {
				tree[index] += delta;
				index += lowbit(index);
			}
		}
	
		// 查询操作：获取[1, index]的前缀和（index是1-based）
		T query(int index) const {
			if (index < 0 || index > n) {
				throw std::out_of_range("Index out of range");
			}
			T sum = 0;
			while (index > 0) {
				sum += tree[index];
				index -= lowbit(index);
			}
			return sum;
		}
	
		// 获取[a, b]区间的和（a和b都是1-based）
		T rangeQuery(int a, int b) const {
			if (a < 1 || b < a || b > n) {
				throw std::out_of_range("Invalid range");
			}
			return query(b) - query(a - 1);
		}
	
		// 获取数组大小
		int size() const {
			return n;
		}
	
		// 清空树状数组
		void clear() {
			std::fill(tree.begin(), tree.end(), 0);
		}
};