C++實作線段樹求區間和-區間查詢

代碼如下：

#include <iostream>
using namespace std;
const int N = 10010;
int input[N];

struct node {
	int l, r;
	int sum;
} tree[4 * N];


void build(int l, int r, int u)//建樹
 {
	tree[u].l = l;
	tree[u].r = r;
	if (l == r) {
		tree[u].sum = input[l];
		return ;
	}
	int mid = (l + r) >> 1;
	build(l, mid, 2 * u);
	build(mid + 1, r, 2 * u + 1);
	tree[u].sum = tree[2 * u].sum + tree[2 * u + 1].sum;
}

int query(int l, int r, int u)//查詢[l,r]的所有元素總和
 {
	if (tree[u].l >= l && tree[u].r <= r) {
		return tree[u].sum;
	}
	if (tree[u].r < l || tree[u].l > r)
		return 0;
	int s = 0;
	if (tree[2 * u].r >= l)
		s += query(l, r, 2 * u);
	if (tree[2 * u + 1].l <= r)
		s += query(l, r, 2 * u + 1);
	return s;
}


int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> input[i];
	build(1, n, 1);
	int cnt;
	cin >> cnt;
	while (cnt--) {
		int a, b;
		cin >> a >> b;
		cout << query(a, b, 1) << endl;
	}
	return 0;
}