Posted on 2011-03-19 21:59
Mato_No1 閱讀(1354)
評論(1) 編輯 收藏 引用 所屬分類:
樹狀數組
樹狀數組與線段樹不同，它只能直接支持前綴區間（[1..r]）或后綴區間（[l..N]）上的操作，而對于一般區間（[l..r]）上的操作則需要通過兩步操作間接完成：先對[1..r]進行操作再對[1..l-1]進行反操作（如加c的反操作就是減c），對于加法操作這樣可反的操作是可以，而對于求最值這樣的不可反的操作（無法通過[1..r]的最值與[1..l-1]的最值得出[l..r]的最值），就沒有辦法了。其實，用樹狀數組是可以解決離線RMQ問題的，但時間復雜度不太理想（一次操作的理論時間復雜度達O((logN)^2)）。
方法是（這里C[i]表示i管轄的數組結點中的最值）：設r'為目前的右端點，一開始r'=r。每次找到r'管轄的數組結點中最左邊的那個的下標（即r' - (r' & (-r')) + 1），設為x。若x>=l，則將C[r']與目前的最值比較、更新，再將r'設為(x-1)；若x<l，則調出A[r']的值與目前最值比較、更新，然后將r'減1。如此直至r'<l為止。
本算法編程復雜度極低，但由于時間效率較低，難以適應較大范圍數據（N, M>100000基本上就TLE了）