用python写一个线段树
时间: 2024-05-03 14:22:36 浏览: 19
以下是一个基本的线段树实现,可以用于区间求和和区间最大值等操作:
```python
class SegmentTree:
def __init__(self, arr):
self.n = len(arr)
self.tree = [0] * (4 * self.n)
self.build_tree(arr, 1, 0, self.n - 1)
def build_tree(self, arr, node, start, end):
if start == end:
self.tree[node] = arr[start]
else:
mid = (start + end) // 2
self.build_tree(arr, 2 * node, start, mid)
self.build_tree(arr, 2 * node + 1, mid + 1, end)
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def update(self, index, val):
self.update_tree(1, 0, self.n - 1, index, val)
def update_tree(self, node, start, end, index, val):
if start == end:
self.tree[node] = val
else:
mid = (start + end) // 2
if start <= index <= mid:
self.update_tree(2 * node, start, mid, index, val)
else:
self.update_tree(2 * node + 1, mid + 1, end, index, val)
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def query(self, left, right):
return self.query_tree(1, 0, self.n - 1, left, right)
def query_tree(self, node, start, end, left, right):
if left > end or right < start:
return 0
elif left <= start and right >= end:
return self.tree[node]
else:
mid = (start + end) // 2
return self.query_tree(2 * node, start, mid, left, right) + \
self.query_tree(2 * node + 1, mid + 1, end, left, right)
```
其中,build_tree用于构建线段树,update用于更新某个节点的值,query用于查询区间和。在使用时,先创建一个SegmentTree对象,然后通过update方法更新某个节点的值,通过query方法查询区间和。例如:
```python
arr = [1, 2, 3, 4, 5, 6, 7, 8]
st = SegmentTree(arr)
print(st.query(1, 4)) # 输出10,即arr[1]+arr[2]+arr[3]+arr[4]的和
st.update(3, 10)
print(st.query(1, 4)) # 输出20,即arr[1]+arr[2]+arr[3]+arr[4]+arr[3]的和
```