相关疑难解决方法(0)

正式地,范围最小查询问题是:

给定一个数组A [0,N-1],找到任意两个给定索引之间具有最小值的元素的位置.

现在,标准解决方案是使用分段树,这里已经描述过了.用于解决范围查询的另一个数据结构是二进制索引树(Fenwick树),它更容易理解和编码.

可以通过二叉索引树来解决范围最小查询问题,以及如何解决？将理解更新和查询功能的实现.

该RMQ问题可以扩展如下所示:

给定是一个n整数数组A.

query(x,y):给定两个整数1≤ x,y≤ n,找到最小值A[x], A[x+1], ... A[y];

更新(X,V):给定的整数v和1≤ x≤ n做A[x] = v.

O(log n)对于使用分段树的两个操作,可以解决该问题.

这是纸上的有效解决方案,但在实践中,分段树涉及大量开销,尤其是在递归实现时.

我知道有一种方法可以解决O(log^2 n)使用二进制索引树的操作中的一个(或两个,我不确定)的问题(可以找到更多的资源,但是这个,这是,IMO,分别是最简洁和详尽的).对于n适合内存的值,此解决方案在实践中更快,因为BIT具有更少的开销.

但是,我不知道如何使用BIT结构来执行给定的操作.我只知道如何使用它来查询区间总和.我怎样才能用它来找到最小值？

如果它有帮助,我有其他人编写的代码可以满足我的要求,但我无法理解它.这是一段这样的代码:

int que( int l, int r ) {
    int p, q, m = 0;

    for( p=r-(r&-r); l<=r; r=p, p-=p&-p ) {
        q = ( p+1 >= l ) ? …

我正在尝试解决Codility 的最小平均两片问题。

我想出了以下代码：

def solution(S, P, Q):
    weights = {'A': 1, 'C': 2, 'G': 3, 'T': 4}
    retVal = []
    for i in range(0, len(P)): 
        if P[i] == Q[i]: 
            retVal.append(weights[S[P[i]]])
        else: 
            retVal.append(local_min(S, weights, P[i], Q[i]))
    return retVal

minimums = {}
def local_min(S, weights, start, end):
    minVal = weights[S[start]]
    for i in range(start,end+1):
        val = weights[S[i]]
        if val == 1: 
            minimums[i] = 1
            return 1
        if val < minVal: 
            minVal = val
        minimums[i] = minVal
    return minVal

这在正确性方面工作得很好，但是它的时间复杂度为 ，O(n*m) …