线段树 算法

基础知识

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

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

适用场景

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

# 点的更新
class Tree:
    
    def __init__(self,n):
        self.st = [0]*(4*n)
    
    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])
    
    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

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

小结

题目概述

2407.最长递增子序列 II

题目详解

300.最长递增子序列

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

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

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