課前提醒希望

記好筆記我會畫很多幫助理解的圖，由于技術原因沒有畫在PPT上內容很散但是十分有用，注意回去繼續(xù)理解區(qū)間詢問經典的區(qū)間詢問有：RMQ、GSS1讓

先來看一下例子，尋找他們的共同點RMQRMQ：給數列a1,a2,..,an和若干詢問(l,r)，回答區(qū)間最小值存在O(N

logN)預處理

O(logN)單次詢問以及O(N

logN)預處理

O(1)單次詢問GSS1GSS1：給數列a1,a2,..,an和若干詢問(l,r)，回答區(qū)間[l,r]中最大連續(xù)和該利用什么性質？存哪些量？修改同時，區(qū)間詢問又伴隨著修改常見的修改有：單點修改、整段修改區(qū)間查詢遇到的數據結構問題往往是區(qū)在競賽中，間查詢比較簡單的情況是在一維的往往也可以變成樹上的詢問（不要怕，很多樹上問題都可以變成一維的）關鍵的性質往往一個量好不好求，取決于它有哪些性質常用的性質有：交換律、結合律、求逆等等RMQRMQ：給數列a1,a2,..,an和若干詢問(l,r)，回答區(qū)間最小值RMQ式是使用線段樹，每個節(jié)點記錄該區(qū)第間最小值段樹的每個節(jié)點上，可以進行合并為什么可以這么做？因為結合律！RMQ在這里結合律的意思是，計算min這個函數，可以不按照從左到右的順序min{a1,

a2,

...,

an}=

min{min{a1,

a2,

..,

a_i},

min{a_{i+1},

..,

an}}RMQ因此可以利用線段樹分開計算，再合并這也是使用線段樹最最基本的條件：計算結果可以拆分再合并（結合律）RMQ結合律只是一個最基本的性質min函數有更加強大性質使得可以做到O(1)單次詢問RMQ發(fā)現(xiàn)：如果知道m(xù)in{a1,a2,a3,a4}和min{a3,a4,a5,a6}就能算出min{a1,..,a6}也就是說

可以合并有交的區(qū)間RMQ因此，就容易得到O(N

logN)-O(1)的算法首先計算一個數組f[i][j]表示從第i個數開始，在區(qū)間[i,i+2^j-1]內的最小值f[i][j]可以通過f[i][j-1]和f[i+2^{j-1}][j-1]遞推得到RMQ對于區(qū)間詢問[l,r]首先得到一個k，2

*

2^k>=區(qū)間長度那么區(qū)間可以被兩個2^k的區(qū)間覆蓋，一個以l開頭，一個以r結尾而這兩個最小值 都已經存了起來，只要O(1)合并即可題外話為什么sum比min好求？由于sum好求逆，也就是說sum(l,r)=sum(1,r)-sum(1,

l-1)而對于min(l,

r)則沒有這個性質因此求和往往很簡單GSS1GSS1：給數列a1,a2,..,an和若干詢問(l,r)，回答區(qū)間[l,r]中最大連續(xù)和該記錄哪些區(qū)間詢問，用線段樹！量？GSS1考慮對于一個區(qū)間[l,r]，將其分為兩個區(qū)間[l,m]和[m+1,

r]最大值可能產生于哪里？GSS1第一種情況是來自[l,m]或者[m+1,

r]之內，這種情況直接利用已經算好的信息即可否則會兩個子區(qū)間，那么一定為[l,m]從右開始連續(xù)的最大和加上[m+1,r]從左開始連續(xù)的最大和GSS1再來看如何遞推求從左開始的最大連續(xù)和、以及從右開始的最大連續(xù)和同樣考慮將其分為兩個區(qū)間[l,m]和[m+1,r]GSS1[l,r]從左開始連續(xù)最大和也有兩種不

：則為[l,

m]

從左開始連續(xù)最大和：則為[l,m]的和加上[m+1,r]里從左開始連續(xù)最大和GSS1因此 只需要 四個量：區(qū)間和、從左最大連續(xù)和、從右最大連續(xù)和、區(qū)間內最大連續(xù)和詢問也通過一樣的方法合并請大家一定要寫出這道題單點修改單點修改是線段是很容易做到的因為 最多會修改O(log

N)個區(qū)間例子：GSS1中加入把某個位置i取負做法：遞歸到最底層，然后自底向上更新區(qū)間修改線段樹的區(qū)間修改往往稍難一些原因在于，如果

遞推修改每個區(qū)間，要修改的區(qū)間會達到O(N)級別區(qū)間修改事實上，

不用遞歸到全部區(qū)間線段樹的一個重要性質：每個區(qū)間都會被更大可以把原區(qū)間分解成O(logN)的區(qū)間覆蓋，個區(qū)間利用懶標記！懶標記？區(qū)間修改拿一個例子來說，在GSS1中加入修改：把一個區(qū)間[l,r]的所有數都變成x做法：懶標記！簡單來說，就是只修改當前需要的區(qū)間，不需要的之后再說。區(qū)間修改懶標記：lazy變量并不一定是bool型，可能會根據問題不同而不同，或者lazy本身就會有很多屬性比如：在剛才的GSS1中加入區(qū)間操作，該怎么做？比較難的區(qū)間修改總的來說，區(qū)間修改基本都是通過懶標記完成不能用懶標記的情況，經過轉換也能使用例如：NOI2012

魔幻棋盤一維魔幻棋盤給出一列數A[1],

A[2],..,A[n]，你需要支持下面兩種操作：修改一個區(qū)間[l,r]，將每個值都加上c詢問區(qū)間[l,r]的最大公約數一維魔幻棋盤如果沒有修改，問題十分簡單加入修改，懶標記似乎不work？是否可以進行適當的轉化，使得懶標記適用？一維魔幻棋盤(a,

b)

=(a,

b

-

a)利用 的性質！那么：(a1,

a2,

..

an)

=(a1,

a2

-

a1,

..,

an

-

a{n-1})一維魔幻棋盤也就是說，每次求[l,

r]區(qū)間的

， 需要A[l]這個值，以及A[i]-A[i-1]的因此可以分開

A[i]的單值和A[i]

-

A[i-1]的區(qū)間

！A[i]

-

A[i-1]的區(qū)間

變成了單點修改一維魔幻棋盤A[l]：普通的線段樹A[i]-A[i-1]：對于[l,r]加上c，相當于A[l]-A[l-1]加上c，A[r+1]-A[r]減去c分解為了兩個單點修改一維版本解決，二維先跳過更進一步當修改不僅僅是單點/區(qū)間修改還有列入：在某個位置

、刪除一個數例如：GSS1+、刪除某個位置的數刪除修改區(qū)間，幾乎可以解決一法是用Splay維的所有問題如果可以請盡量采用這種方法是不是太復雜了？換個想法？離線？刪除修改（或者被刪除后），用一個占位符如果

能夠預先留出位置給每個即將

的數在沒有代替那么還是簡單的區(qū)間問題其他數據結構二維線段樹（一般都用樹套樹，更實用方便）其他數據結構平衡樹，只需要知道