灯神视频讲解线段树
【题目】给定一个数组arr，数组可能非常大。在程序运行过程中，你可能要做好几次query和update操作：
1.query(arr, L, R) 表示计算数组arr中，从下标L到下标R之间的所有数字的和。
2.update(arr, i, val) 表示要把arr[i]中的数字改成val。

#include<cstdio>
const int maxn = 1e3+5;
//建树 
void build_tree(int arr[], int tree[], int node, int start, int end){
	if(start == end){
		tree[node] = arr[start]; //这里是tree[node]注意别写错了 
	}else{
		int mid = (start + end) / 2;
		int left_node = 2 * node + 1;
		int right_node = 2 * node + 2;
		build_tree(arr, tree, left_node, start, mid);
		build_tree(arr, tree, right_node, mid + 1, end);
		tree[node] = tree[left_node] + tree[right_node];
	}
}
//更新
void update(int arr[], int tree[], int node, int start, int end, int idx, int val){
	if(start == end){
		arr[idx] = val;
		tree[node] = val;
	}else{
		int mid = (start + end) / 2;
		int left_node = 2 * node + 1;
		int right_node = 2 * node + 2;
		if(idx>=start && idx <= mid){
			update(arr, tree, left_node, start, mid, idx, val);
		}else{
			update(arr, tree, right_node, mid+1, end, idx, val);
		}
		tree[node] = tree[left_node] + tree[right_node];
	}
}
//查询
int query(int arr[], int tree[], int node, int start, int end, int L, int R){
	if(R < start || L > end) return 0;
	else if(L<=start && R<= end) return tree[node];
	else if(start == end) return tree[node];
	else{
		int mid = (start + end) / 2;
		int left_node = 2 * node + 1;
		int right_node = 2 * node + 2;
		int sum_left = query(arr, tree, left_node, start, mid, L, R);
		int sum_right = query(arr, tree, right_node, mid+1, end, L, R);
		return sum_left + sum_right;
	}
} 
int main(){
	int arr[]={1,3,5,7,9,11};
	int size = 6;
	int tree[maxn]={0};
	build_tree(arr, tree, 0, 0, size-1);
	update(arr, tree, 0, 0, size-1, 4, 6);
	for(int i=0;i<15;i++){
		printf("tree[%d]=%d\n",i, tree[i]);
	}
	int s= query(arr, tree, 0, 0, size-1, 2, 5);
	printf("%d\n", s);
	return 0;
}