lipog / algorithm Goto Github PK

RMQ通过O(nlogn)的时间复杂度构建一个dp二维数组，可以在O(1)的时间内查找到数据
使用dp[i][j]表示从第i位数（index从1开始算）开始，连续2^j个数中的最小值。求dp[i][j]的时候是分为两部分的，第一部分是从 i 到 i + 2^(j - 1) - 1，第二部分从i + 2 ^ (j - 1) 到 i + 2^j - 1，因为二进制数中，前一个数是后一个数的两倍，那么可以把 i 到 i + 2^j - 1这个区间，通过 2^(j - 1)分为两个相等的部分，那么转移方程就可以得出来了
dp[i][j] = min(dp[i][j-1], dp[i + (1 << j - 1)][]j - 1)，其中减号 - 的优先级高于 <<
因此构造RMQ的代码为：
func rmq_init(arr []int) [][]int {
dp := make([][]int, len(arr) + 1)
for k, _ := range dp {
dp[k] = make([]int, len(arr) + 1)
}
//因为下标从1开始计算，所以要多构造一个位置
for i := 1; i <= len(arr); i++ {
dp[i][0] = arr[i]
}
for j := 1; (1 << j) <= len(arr); j++ {
for i := 1; i + (1 << j) - 1 <= len(arr); i++ {
dp[i][j] = min(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1])
}
}
}