Permutation 1...N. Answer queries "How many numbers between [X,Y] position are in the interval [L,K]"? So I am solving this task:
We have an permutation of the numbers 1..n. 
I need to answer m queries:
-How many numbers between X-th and Y-th position are in the interval [L,K] (&lt;=k and >= L)?

So my solution is simple: I create a segment tree and in every node i keep an map -> which numbers are in this interval and the position (when they are sorted).

For example ( 98, 14 , 22, 45, 33) the map for this interval is (14,1)(22,2),(33,3),(45,5)..
Then when i recieve a query (X,Y,l,k) I find the interval in the tree,then I use lower bound (to the map in the node (so i get Log(n) time complexity)) to find the closest element to l and the closest element to k and substract their positions. The solution works, but i exceed the time for some test. Any tips how can i make it faster ? Maybe faster way to create the maps in the nodes ? Or faster search in the tree? 

#include &lt;iostream&gt;
#include &lt;map&gt;
using namespace std;

#define IntervalsIntersect(left,right,X, Y)  (left &lt;= Y &amp;&amp; right &gt;= X)

struct node
{
    map&lt;int, int&gt; m;
};

int getNextIndRight(int ind, int n) // By going right how does the interval changes
    {
    int diff = n - ind;
    if (diff % 2 == 0)
        return n - diff / 2;
    return n - diff / 2 - 1;

}
int getNextIndLeft(int ind, int n)
{
    int diff = n - ind;
    if (diff % 2 == 0)
        return ind + 1 + diff / 2;
    return (ind + diff / 2) + 1;
}
void build(int* a, node* t, int v, int tl, int tr, int left, int right)
{
    if (tl == tr)
    {
        t[v].m.insert(pair&lt;int, int&gt;(a[tl], 1));
    }
    else
    {
        int tm = (tl + tr) / 2;
        build(a, t, v * 2, tl, tm, left, getNextIndRight(left, right));
        build(a, t, v * 2 + 1, tm + 1, tr, getNextIndLeft(left, right), right);
        t[v].m = t[v * 2].m;
        t[v].m.insert(t[v * 2 + 1].m.begin(), t[v * 2 + 1].m.end());
        int i = 1;
        for (auto &amp;p : t[v].m)
        {
            p.second = i++;
        }

    }
}

int countInInterval(map&lt;int, int&gt;&amp; m, int k, int l)
{

    //for (auto &amp;p : m) 
    //    cout&lt;&lt;p.first&lt;&lt;" "&lt;&lt;p.second&lt;&lt;endl;
    auto it = m.lower_bound(k);
    auto it2 = m.lower_bound(l);

    bool firstOK = it != m.end();
    bool secondOK = it2 != m.end();
    if (!firstOK &amp;&amp; !secondOK)
        return 0;
    else if (firstOK &amp;&amp; !secondOK)
        return m.size() - it-&gt;second + 1;

    if (it == it2)
    {
        if (k &lt;= it-&gt;first&amp;&amp;it-&gt;first &lt;= l)
            return 1;
        return 0;
    }

    int res= (it2-&gt;second - it-&gt;second);
    if (k &lt;= it2-&gt;first &amp;&amp; it2-&gt;first &lt;= l)
        res++;
    return res;

}
bool hasIntersection(int left, int right, int X, int Y)
{
    return left &lt;= Y &amp;&amp; right &gt;= X;
}
int f(node* t, int* a, int left, int right, int n, int v, int X, int Y, int k, int l)
{
    if (left &gt;= X &amp;&amp; right &lt;= Y)
        return countInInterval(t[v].m, k, l);
    int leftFirst = left;
    int rightFirst = getNextIndRight(left, right);
    int res = 0;
    if (IntervalsIntersect(leftFirst, rightFirst, X, Y))
        res += f(t, a, left, getNextIndRight(left, right), n, v * 2, X, Y, k, l);

    int leftsecond = getNextIndLeft(left, right);
    int rightsecond = right;
    if (IntervalsIntersect(leftsecond, rightsecond, X, Y))
        res += f(t, a, getNextIndLeft(left, right), right, n, v * 2 + 1, X, Y, k, l);;
    return res;
}

int main()
{


    int n, m;
    cin &gt;&gt; n &gt;&gt; m;
    int* a = new int[n];
    for (int i = 0; i &lt; n; i++)
        cin &gt;&gt; a[i];


    node* t = new node[4 * n + 1];

    build(a, t, 1, 0, n - 1, 1, n);


    for (int i = 0; i &lt; m; i++)
    {
        int x, y, k, l;
        cin &gt;&gt; x &gt;&gt; y &gt;&gt; k &gt;&gt; l;
        cout &lt;&lt; f(t, a, 1, n, n, 1, x, y, k, l) &lt;&lt; endl;

    }


}
I believe the problem lies in the initialization time. If I am not wrong it is like O(n^2 log n) which might be a problem for tests with large n and small sample size.

To fix it you'll have to redo the whole algo if I am not mistaken.

There is a method that doesn't have the same long initialization problem while retaining the same O(log n) (at least on average, O(log^2 n) at worst) time per iteration - simply build a two dimensional segment tree. Since we work with a permutation it will be rather sparse.