线段树 实现局部更新
原创
线段树是把数组构建一个棵满二叉树的形式, 然后通过局部的更新,在数组求和的情况下可以通过log(n)的时间复杂，快速实现局部求和的。
在构建满二叉树的过程中，会对树进行分解，不断地二分。
可以这么理解，树的根节点就是整个数组的和，然后把数组二分，左子树是数组前半部分的和，右子树是数组后半部分的和。
数组原数据都在叶子节点，非叶子节点是左右子树的和。
例如给定一个输入数组[1,5,3,7,3,2,5,7]， 构建的线段树如下图所示
python实现的线段树如下
class LineTree(object):
def __init__(self, arr):
self.n = len(arr)
m = self.n + 1
self.arr = [0] * m
for i in range(1, m):
self.arr[i] = arr[i - 1]
self.size = m * 4
self.tree = [0] * self.size
self.mark = [0] * self.size
def build(self, l, r, p):
if l == r:
self.tree[p] = self.arr[l]
return
mid = int((l + r) / 2)
self.build(l, mid, 2 * p)
self.build(mid + 1, r, 2 * p + 1)
self.tree[p] = self.tree[2 * p] + self.tree[2 * p + 1]
def update(self, l, r, ll, rr, p, dd):
if l <= ll and r >= rr:
self.mark[p] = dd
self.tree[p] = self.tree[p] + dd * (rr - ll + 1)
else:
mid = int((ll + rr) / 2)
self.push_down(ll, rr, p)
if l <= mid:
self.update(l, r, ll, mid, 2 * p, dd)
if r > mid:
self.update(l, r, mid + 1, rr, 2 * p + 1, dd)
self.tree[p] = self.tree[2 * p] + self.tree[2 * p + 1]
def push_down(self, l, r, p):
mid = int((l + r) / 2)
self.mark[2 * p] = self.mark[p]
self.mark[2 * p + 1] = self.mark[p]
self.tree[2 * p] = self.tree[2 * p] + (mid - l + 1) * self.mark[2 * p]
self.tree[2 * p + 1] = self.tree[2 * p + 1] + (r - mid) * self.mark[2 * p + 1]
self.mark[p] = 0
def qury(self, l, r, ll, rr, p):
if l <= ll and r >= rr:
return self.tree[p]
else:
self.push_down(ll, rr, p)
mid = int((ll + rr) / 2)
ans1 = 0
ans2 = 0
if l <= mid:
ans1 = self.qury(l, r, ll, mid, 2 * p)
if r > mid:
ans2 = self.qury(l, r, mid + 1, rr, 2 * p + 1)
return ans1 + ans2
if __name__ == '__main__':
arr = [1, 2, 3, 4, 5, 6]
tree = LineTree(arr)
tree.build(1, tree.n, 1)
print("origin tree: ", tree.tree)
print("mark info: ", tree.mark)
tree.update(1, 4, 1, tree.n, 1, 1)
print("after update mark: ", tree.mark)
print("after update tree: ", tree.tree)
re = tree.qury(1, 5, 1, tree.n, 1)
print("manu cal: ", sum(arr[:5]) + 4)
print("tree result: ", re)运行结果：
origin tree: [0, 21, 6, 15, 3, 3, 9, 6, 1, 2, 0, 0, 4, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
mark info: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
after update mark: [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
after update tree: [0, 25, 9, 16, 3, 3, 10, 6, 1, 2, 0, 0, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
manu cal: 19
tree result: 19
更多内容请关注微信公众号： IT技术漫漫谈
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。