线段树 算法

基础知识

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

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

适用场景

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

# 点的更新
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

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

小结

题目详解

300.最长递增子序列

这个题目是方便我们做下面的 最长递增子序列

思路分析：这个最长递增子序列，我们采用动态规划进行求解，
dp[i]的定义：以nums[i]为结尾的子序列的最长的长度
有递推公式：
$dp[i]=max(dp[i],dp[j]+1)$,当我们遍历前$i-1$个元素，当满足$nums[j]<=nums[i]$的时候更新
时间复杂度分析：是o(n^2)

2407.最长递增子序列 II

2407.最长递增子序列 II

思路分析：这个题目首先想到可以使用动态规划，但是如果内层的的判断i之前的满足的情况的时候还是使用暴力进行求解的话，就会出现超时的情况，所以我们就得考虑使用线段树，线段树对于求解区间的最值的时间复杂度只有o(logn)

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        ans = 1
        
        # dp[i][j] 表示前i个元素中，以值j结尾的长度的子序列长度的最大值
        # 注意，这里的j是值域
        tr = Tree(100005)
        # 这个求解的是外层循环i
        for va in nums:
            if va != 1:
            	# 确保这个zuo没有超过范围
                zuo = max(1,va-k)
                you = va-1
                # 1为根节点
                # 这个是求解的内层循环j
                pre = tr.query(1,1,100000,zuo,you)
                now = pre+1
                ans = max(ans,now)
                tr.update(1,1,100000,va,now)
            else:
                tr.update(1,1,100000,1,1)
        return ans

# 线段树模版
class Tree:

    def __init__(self,n):
        self.t = [0] * (n*4)
    def update(self,o,l,r,index,va):
        if l==r:
            self.t[o] = va
            return 
        m = (l+r) //2
        if index<=m:
            self.update(o*2,l,m,index,va)
        else:
            self.update(o*2+1,m+1,r,index,va)
        self.t[o] = max(self.t[o*2],self.t[o*2+1])

    def query(self,o,l,r,L,R):
        if l>=L and r<= R:
            return self.t[o]
        m = (l+r) // 2
        res = 0
        if m >= L:
            res = max(res,self.query(o*2,l,m,L,R))
        if R>m:
            res = max(res,self.query(o*2+1,m+1,r,L,R))
        return res

3.异或和

3.异或和

思路分析：由于节点的数目和操作的次数太多，所以并不可能暴力求解，对于频繁的区间查询与更新的话，还是得使用线段树进行操作，但是你的节点得能够在数组中进行存储，并且你的存储关系要能够体现你的节点之间的父子关系！

# 首先获取输入
n,m = map(int,input().split())

# 获取节点的值
a = list(map(int,input().split()))
# 首先将0插入到第一个元素，这样下标i就对应对应的节点
a = [0] + a

# 使用邻接表进行存储边的情况
sto = [ [] for _ in range(n+1) ]

# 使用邻接表存储边
for _ in range(n-1):
    u,v = map(int,input().split())
    sto[u].append(v)
    sto[v].append(u)

# 记录树的节点的范围，这个是映射的问题，实际上只有le[i]是存储数字的
le = [0] * (n+1)
ri = [0] * (n+1)

cnt = 0

# fa 是 u 的父亲结点，避免到u->fa的情况陷入无限递归
# 深度搜索
def dfs(fa,u):
    # 说明这个是全局的变量
    global cnt
    cnt += 1
    le[u] = cnt
    for v in sto[u]:
        # 判断是否是父亲节点
        if v == fa:
            continue
        dfs(u,v)
    cnt += 1
    ri[u] = cnt


dfs(0,1)

class Tree:

    def __init__(self,n):
        self.t = [0] * (4*n)
    # 当前的节点o,当前的区间l,r, 在index 更新值为va
    def update(self,o,l,r,index,va):
        if l==r:
            self.t[o] = va
            return
        m = (l+r)//2
        if index <=m :
            self.update(o*2,l,m,index,va)
        else:
            self.update(o*2+1,m+1,r,index,va)
        self.t[o] = self.t[o*2] ^ self.t[o*2+1]
    # 当前的节点o,当前的区间l,r, 查询的区间是L,R
    def query(self,o,l,r,L,R):
        if l>=L and r <=R:
            return self.t[o]
        m = (l+r)//2
        ans = 0
        if m>=L:
            ans ^= self.query(o*2,l,m,L,R)
        if R>m:
            ans ^= self.query(o*2+1,m+1,r,L,R)
        return ans

tr = Tree(cnt)
# 先进行初始化操作
for i in range(1,n+1):
    # 更新值操作，当前的节点o,当前的区间l,r,需要在le[i] 更新值为a[i]
    tr.update(1,1,cnt,le[i],a[i])

for _ in range(m):
    b = list(map(int,input().split()))
    if b[0] == 1:
        tr.update(1,1,cnt,le[b[1]],b[2])
        a[b[1]] = b[2]
    else:
        u = tr.query(1,1,cnt,le[b[1]],ri[b[1]])
        print(u)