线段树与树状数组详解：原理、应用场景及代码实现

线段树与树状数组详解：原理、应用场景及代码实现

引用

CSDN

1.

https://blog.csdn.net/weixin_74850661/article/details/145394365

基础知识

线段树和树状数组都只是一个工具，题目并不会一下子就告诉你这个题目用到线段树和树状数组，这取决于你想使用的数据结构以及所要优化的方向。

线段树和树状数组（也称为二叉索引树）是两种常用的数据结构，主要用于处理数组的区间查询和更新操作。它们的主要区别如下：

适用场景

• 线段树 ：
  • 适用于需要复杂区间操作的场景，如区间最大值、区间最小值、区间更新等。
  • 适合动态性较强的问题。

# 点的更新
class Tree:
    
    def __init__(self,n):
        self.st = [0]*(4*n)
    # 当前节点o,当前范围是l,r，需要在索引index，更新值为val
    def update(self,o,l,r,index,val):
        # l,r 是当前区间的范围，index 是要插入的数据的索引
        if l==r:
            self.st[o] = val
            return 
        mid = (l+r)//2
        if index<=mid:
            self.update(2*o,l,mid,index,val)
        else:
            self.update(2*o+1,mid+1,r,index,val)
        self.st[o] = max(self.st[2*o],self.st[2*o+1])
    # 当前节点为o,当前的节点为l,r,需要查询的范围是L,R
    def query(self,o,l,r,L,R):
        if l >= L and r <= R:
            return self.st[o]
        mid = (l+r)//2
        res = 0
        if L<=mid:
            res = max(res,self.query(2*o,l,mid,L,R))
        if R > mid:
            res = max(res,self.query(2*o+1,mid+1,r,L,R))
        return res

• 树状数组 ：
  • 适用于简单的前缀和查询和单点更新问题。
  • 适合静态或半静态问题，且代码实现更简洁。