recursion - 性能问题：段树、更新函数

Question

我用这样的功能更新段树。分析说这是瓶颈：

void update (int tree[], int root, int left, int right, int pos, double val)
{
    if (left == right)
    {
        data[tree[root]] = val;
    }
    else
    {
        int middle = (left + right) / 2;
        if (pos <= middle)
            update(tree, root*2, left, middle, pos, val);
        else
            update(tree, root*2+1, middle+1, right, pos, val);
        tree[root] = indexOfMax(tree, tree[root*2], tree[root*2+1]); // simple comparations
    }
}
// indexOfMax is just a simple comparation
int indexOfMax(int tree[], int a, int b)
{
    //cout << data[tree[a]] << " > " << data[tree[b]] << " ? " << tree[a] << " : " << tree[b] << endl;
    return data[a] > data[b] ? a : b;
}

虽然内存操作很快，但我想知道它是否是由递归开销引起的，而它的深度通常不会超过 20。

我从原始分析器中得到的是：

• 4.39434ms - 对数据进行单次二进制搜索的平均时间
• 2642.94ms - 一次更新的时间
• 19.9097ms - 单个 RMQ 查询的时间。

所以.. 一次更新所花费的时间是戏剧性的:)。

答案：找到了一个隐藏的 std::find over map。