本条目持续更新中
线段树 1 : 建树 单点修改 区间求和
关于线段树:假如我们有这样一个数列 3 3 2 8 0 7 2 1
那我们就可以建一个线段树 大概长这样:
由图可知 编号为i的左子树编号为2i 右子树编号为2i+1
我们用k代表根 用ls代表k的左子树 用rs代表k的右子树 mid为当前k涵盖区间的中点 则有:
建树
容易看出 对于一个根k 它的值即为ls与rs的和 所以我们先递归ls 再递归r's 最后处理k
每次递归长度减少一半 当区间长度为1时返回原数组中对应位置
单点修改
我们首先查找出这个点处在的叶的位置 然后从下往上更新
区间求和
假设我们要求的区间为[x,y] 那么我们考虑当前k所包含的区间[l,r]与[x,y]的关系:
1.[x,y]包含[l,r] 那么就直接将s[k]加入答案中
2.[x,y]不包含[l,r] 那么就以mid为界 将[x,y]分成两段区间 然后分别递归ls rs