動機
記錄用
區間問題是?
就是給個數列，之後做 修改、查詢
不論修改、查詢都可以做 單點、範圍
分類
- 區間修改、區間查詢：線段樹 + 懶人標記
- 區間修改、單點查詢：BIT + 差分
- 單點修改、區間查詢：線段樹／BIT
- 區間修改、沒有查詢：差分
- 沒有修改、區間查詢：前綴和／稀疏表
差分
做很多次區間修改，之後一直查詢
有沒有一種方法可以讓修改影響到右邊的數字? 這就要提到差分的特性。
差分定義成D_i = A_i - A_i-1
根據上面的定義可以看到如果sum(D[x] for x in range(i))，就會是A_i，因為其他值會被差分扣掉
所以只要D_i的其中一個有被加新數字，就會影響到這個數字!!
這樣如果要修改range([l,r))就是D_l + diff 與 D_r - diff，之後做prefix sum就能回答了!!
離散化
之前有提到分塊，也就是把資料分組
離散化就是把資料再細分，像是如果數字有重複，就依據原本的位置再上新的編號
LCA 與 Range Minimum Query
如果把一顆tree用dfs走一遍，並在每一次遇到時記下點的編號 並把第一次的編號當成該點的position
idx = []
pos = {}
acc = 0
def dfs(root):
if root:
idx.append(acc)
pos[root] = acc if root not in pos else pos[root]
[dfs(child) for child in root.children]
那這樣LCA就是在idx中pos[a] ~ pos[b]範圍的最小值，因為從a到b一定會過LCA，同時LCA也是pos最小的!!