树状数组维护区间最值问题

树状数组维护区间最值问题"/>

树状数组维护区间最值问题

使用树状数组需要理解其具体原理解析链接，记住其维护的区间是 [ x − l o w b i t ( x ) + 1 , x ] ( x ! = 0 ) [x-lowbit(x)+1,x](x!=0) [x−lowbit(x)+1,x](x!=0) l o w b i t ( x ) = x & ( − x ) lowbit(x)=x\&(-x) lowbit(x)=x&(−x)

1. 维护区间和的时候使用的是前缀和的方式进行维护，依次向上更新
2. 在维护区间最大值的时候使用的是每个 [ x − l o w b i t ( x ) + 1 , x ] ( x ! = 0 ) [x-lowbit(x)+1,x](x!=0) [x−lowbit(x)+1,x](x!=0)区间的更新，所以在统计 [ l , r ] [l,r] [l,r]区间的最值问题时需要依次统计各个子区间 [ l , . . . ] . . . [ r − l o w b i t ( r ) + 1 , r ] [l,...]...[r-lowbit(r)+1,r] [l,...]...[r−lowbit(r)+1,r]区间的最值。
   例：leetcode-接雨水
   该题可以使用树状数组的方式解决，先找出[0,n]之间的最大值h及其下标index，然后分别向左[0,index]和向右[index,n]，计算其区间的最高两个柱子之间的最大值以及能接到的最大雨水。

var bitTree []int
func trap(height []int) int {lent := len(height)bitTree = make([]int, lent+500)index, h := 0, height[0]for i := range height {// fmt.Println(i)if height[i] > h {h = height[i]index = i}add(i, height)}sum := 0//左边for r := index - 1; r >= 0; r-- {for hl := searchMax(0, r, height); height[r] < hl; r-- {sum += (hl - height[r])}}//右边for l := index + 1; l < lent; l++ {for hr := searchMax(l, lent-1, height); height[l] < hr; l++ {sum += (hr - height[l])}}return sum
}func lowbit(x int) int {return x & (-x)
}func max(x, y int) int {if x > y {return x}return y
}func add(x int, height []int) {bitTree[x] = height[x]up := lowbit(x)for i := 1; i < up; i <<= 1 {bitTree[x] = max(bitTree[x], bitTree[x-i])}
}func searchMax(l, r int, height []int) int {ans := height[r]for l < r {ans = max(ans, height[r])for r--; l < r-lowbit(r); r -= lowbit(r) {ans = max(ans, bitTree[r])}}//上面的判断没有将l加入判断ans = max(ans, height[l])return ans
}