线段树的区间求和与区间修改
时间: 2024-06-20 16:02:52 浏览: 11
线段树是一种二叉树形数据结构,适用于动态的区间查询和区间修改。下面给出线段树的区间求和和区间修改的实现方法。
1.区间求和
线段树的区间求和操作可以用递归的方式进行。对于每一个非叶节点,维护一个区间的和,左右儿子分别维护左半区间和右半区间的和。查询区间的时候,用二分的方式进行递归,直到查询的区间和当前节点所维护的区间有交集为止,将左右儿子的和相加即可得到查询区间的和。
2.区间修改
线段树的区间修改可以用懒标记的方式来实现。对于每一个节点,维护一个懒标记,表示这个节点的区间是否被修改过。在对一个区间进行修改时,将懒标记打上,然后递归下去更新左右儿子的区间和,最后将懒标记清空。查询的时候,如果一个节点的懒标记不为空,就先下推懒标记,再递归查询子区间。
参考代码:
区间求和:
```python
class SegmentTree:
def __init__(self, n):
self.n = n
self.tree = * (n*4)
def build(self, node, left, right, nums):
if left == right:
self.tree[node] = nums[left]
return
mid = (left + right) >> 1
self.build(node*2, left, mid, nums)
self.build(node*2+1, mid+1, right, nums)
self.tree[node] = self.tree[node*2] + self.tree[node*2+1]
def query(self, node, left, right, qleft, qright):
if left > qright or right < qleft:
return 0
if left >= qleft and right <= qright:
return self.tree[node]
mid = (left + right) >> 1
return self.query(node*2, left, mid, qleft, qright) + self.query(node*2+1, mid+1, right, qleft, qright)
def update(self, node, left, right, uleft, uright, val):
if left > uright or right < uleft:
return
if left >= uleft and right <= uright:
self.tree[node] += val * (right - left + 1)
if left != right:
self.lazy[node*2] += val
self.lazy[node*2+1] += val
return
mid = (left + right) >> 1
self.update(node*2, left, mid, uleft, uright, val)
self.update(node*2+1, mid+1, right, uleft, uright, val)
self.tree[node] = self.tree[node*2] + self.tree[node*2+1]
```
区间修改:
```python
class SegmentTree:
def __init__(self, n):
self.n = n
self.tree = * (n*4)
self.lazy = * (n*4)
def build(self, node, left, right, nums):
if left == right:
self.tree[node] = nums[left]
return
mid = (left + right) >> 1
self.build(node*2, left, mid, nums)
self.build(node*2+1, mid+1, right, nums)
self.tree[node] = self.tree[node*2] + self.tree[node*2+1]
def query(self, node, left, right, qleft, qright):
if left > qright or right < qleft:
return 0
if left >= qleft and right <= qright:
return self.tree[node]
mid = (left + right) >> 1
self.pushdown(node, mid-left+1, right-mid)
return self.query(node*2, left, mid, qleft, qright) + self.query(node*2+1, mid+1, right, qleft, qright)
def update(self, node, left, right, uleft, uright, val):
if left > uright or right < uleft:
return
if left >= uleft and right <= uright:
self.tree[node] += val * (right - left + 1)
if left != right:
self.lazy[node*2] += val
self.lazy[node*2+1] += val
return
mid = (left + right) >> 1
self.pushdown(node, mid-left+1, right-mid)
self.update(node*2, left, mid, uleft, uright, val)
self.update(node*2+1, mid+1, right, uleft, uright, val)
self.tree[node] = self.tree[node*2] + self.tree[node*2+1]
def pushdown(self, node, leftlen, rightlen):
if self.lazy[node]:
self.tree[node*2] += self.lazy[node] * leftlen
self.tree[node*2+1] += self.lazy[node] * rightlen
self.lazy[node*2] += self.lazy[node]
self.lazy[node*2+1] += self.lazy[node]
self.lazy[node] = 0
```