线段树-Segment tree

O(logn)的查找数组区间和以及修改数组中的值

涉及到的知识点

• 递归
• 完全二叉树

---

其中涉及到的操作

• build_tree()把一个数字构建成一个树
• query_tree()返回L,R一个区间的和
• update_tree(）更改数组中的下标为idx值为val

---

---

完整代码

#include<stdio.h>
#define MAX_LEN 100000
void build_tree(int arr[], int tree[], int node, int start, int end) {
	if (start == end) { //递归出口
		tree[node] = arr[start];
		return;
	}

	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); //[start, mid]的区间
	build_tree(arr, tree, right_node, mid + 1, end);// [mid + 1, end]的区间
	tree[node] = tree[left_node] + tree[right_node]; // 树的结点为左右子结点的和

}

void update_tree(int arr[], int tree[], int node, int start, int end, int idx, int val) {

	if (start == end) { // 递归出口
		arr[idx] = val; // 修改数组的值
		tree[node] = val;// 更改树的结点值
		return;
	}

	int mid = (start + end) / 2;
	int left_node = 2 * node + 1;
	int right_node = 2 * node + 2;

	if (start <= idx && idx <= mid) { //在左子区间
		update_tree(arr, tree, left_node, start, mid, idx, val);
	}
	else  { // 在右子区间
		update_tree(arr, tree, right_node, mid + 1, end, idx, val);
	}

	tree[node] = tree[left_node] + tree[right_node];

}

int query_tree(int arr[], int tree[], int node, int start, int end,int L, int R) {

	if (R < start || L > end) { //不满足区间要求 返回0
		return 0;
	}
	else if (start == end) { //到了叶子结点返回

		return tree[node];
	}
	else if (R >= end && L <= start) { //结点在LR范围之内
		return tree[node];
	}

	int mid = (start + end) / 2;
	int left_node = node * 2 + 1;
	int right_node = node * 2 + 2;
	int sum_left = query_tree(arr, tree, left_node, start, mid, L, R);
	int sum_right = query_tree(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[MAX_LEN] = { 0 };
	build_tree(arr, tree, 0, 0, size - 1);
	
	update_tree(arr, tree, 0, 0, size - 1, 4, 6);

	int s = query_tree(arr, tree, 0, 0, size - 1, 2, 5);
	printf("%d
", s);
	return 0;
}