基础知识

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

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

适用场景

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

# 点的更新
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] = valreturn mid = (l+r)//2if 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)//2res = 0if 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

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

---

小结

特性	线段树	树状数组
结构	二叉树	基于数组的树形结构
功能	支持复杂区间操作	主要用于前缀和查询
时间复杂度	$(O(\log n)$)	$(O(\log n))$
空间复杂度	$(O(4n)$)	$(O(n))$
适用场景	动态区间操作	简单查询和更新

题目概述

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)# 这个求解的是外层循环ifor va in nums:if va != 1:# 确保这个zuo没有超过范围zuo = max(1,va-k)you = va-1# 1为根节点# 这个是求解的内层循环jpre = tr.query(1,1,100000,zuo,you)now = pre+1ans = 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] = vareturn m = (l+r) //2if 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) // 2res = 0if 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