Performance issues : segment tree, update function

Question

I update segment tree with such function. Profiling says here's the bottleneck:

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;
}

And while memory operations are fast, I'm wondering if it is caused by recursion overhead, while the depth of it is usually not more 20.

What I get from my primitive profiler is:

• 4.39434ms - average time for a singe binary search over data
• 2642.94ms - time from a single update
• 19.9097ms - time for a single RMQ-query.

So.. The time spent on a single update is dramatic :).

Answer : one hidden std::find over map was found.