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