基礎知識

線段樹和樹狀數組都只是一個工具來的，題目并不會一下子就告訴你這個題目用到線段樹和樹狀數組，這個取決于你想使用的數據結構以及所要優化的方向

線段樹和樹狀數組（也稱為二叉索引樹）是兩種常用的數據結構，主要用于處理數組的區間查詢和更新操作。它們的主要區別如下：

適用場景

• 線段樹：
  • 適用于需要復雜區間操作的場景，如區間最大值、區間最小值、區間更新等。
  • 適合動態性較強的問題。

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