引入
现在我们要求一个数组进行两个操作
- 任意L到R的和
- 任意更新某个数
首先我们想到可以用前缀和，新建一个数组，保存每个位置到第一位的和
但是算法效率变化了
还有优化空间吗
线段树
线段树可以做到时间复杂度查找更新都是 log n
下面是一个例子
如果我们要找到 2 - 5的和
直接获取[3-5]的和再找到2的值相加即可
构建线段树
给这个树来个二向箔之后我们怎么寻找对应节点的数据？ 下面有个公式
left = 2 * Node + 1 right = 2 * Node + 2
现在我们要求一个数组进行两个操作
首先我们想到可以用前缀和，新建一个数组，保存每个位置到第一位的和
但是算法效率变化了
还有优化空间吗
线段树可以做到时间复杂度查找更新都是 log n
下面是一个例子
如果我们要找到 2 - 5的和
直接获取[3-5]的和再找到2的值相加即可
给这个树来个二向箔之后我们怎么寻找对应节点的数据？ 下面有个公式
left = 2 * Node + 1 right = 2 * Node + 2
