#include <vector>
using std::vector;

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

	// 前缀和查询：求前idx个元素的和
	int pre(int idx) {
		int sum = 0;
		while (idx) {
			sum += tree[idx];
			idx -= idx & -idx; // 向下累加子节点
		}
		return sum;
	}

public:
	FenwickTree(int size) : tree(size + 1, 0), n(size) {}

	void update(int idx, int val) {
		while (idx <= n) {
			tree[idx] += val;
			idx += idx & -idx; // 向上更新父节点
		}
	}

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

int main() {
	return 0;
}