Marge Sort Tree Implementation

/**
 * Author           : Dipu Kumar Mohanto (Dip)
 *                    CSE, BRUR.
 *                    Batch - 6
 *
 * Problem          : Marge Sort Tree Implementation
 * Algorithm        : Marge Sort Tree
 * Compleixty       : build_tree     -> O(logn^2)
 *                    query_tree     -> O(logn^2)
 * Category         : Data Structure
 *
 * Difficulty       : Medium
 *
 * Source           : commonlounge.com
 *                    codechef.com - merge-sort-tree-tutorial
 *
 * Verdict          : OK
 *
 * Date             :
 * E-mail           : dipukumarmohanto1@gmail.com
**/

#include <bits/stdc++.h>

using namespace std;

#define VI                     vector <int>
#define pb                     push_back
#define all(v)                 v.begin(), v.end()

const int mx = 1e5+5;

int arr[mx];

struct nodeTree {
    VI data;

    void assignLeafNode(int num) {
        data.pb(num);
    }

    void marge(nodeTree& leftTree, nodeTree& rightTree) { // marge part, same as
        int len_left = leftTree.data.size();              // marge sort
        int len_right = rightTree.data.size();

        int index_left = 0;
        int index_right = 0;

        while (index_left<len_left && index_right<len_right) {
            if (leftTree.data[index_left] < rightTree.data[index_right]) {
                data.pb(leftTree.data[index_left]);
                index_left++;
            }

            else {
                data.pb(rightTree.data[index_right]);
                index_right++;
            }
        }

        while (index_left<len_left) {
            data.pb(leftTree.data[index_left]);
            index_left++;
        }

        while (index_right<len_right) {
            data.pb(rightTree.data[index_right]);
            index_right++;
        }
    }

    int getRes(int k) {
        return lower_bound(all(data), k) - data.begin();
    }
}tree[mx<<2];



void build_tree(int node, int a, int b)
{
    if (a>b)
        return;

    if (a==b)
    {
        tree[node].assignLeafNode(arr[a]);
        return;
    }
    int left = node<<1;
    int right = node<<1|1;
    int mid = (a+b)>>1;


    build_tree(left, a, mid);
    build_tree(right, mid+1, b);

    tree[node].marge(tree[left], tree[right]);
}


















int query_tree(int node, int a, int b, int i, int j, int k)
{
    if (a>b || a>j || i>b)
        return 0;

    if (a>=i && b<=j)
    {
        return tree[node].getRes(k);
    }
    int left = node<<1;
    int right = node<<1|1;
    int mid = (a+b)>>1;

    int p1 = query_tree(left, a, mid, i, j, k);
    int p2 = query_tree(right, mid+1, b, i, j, k);

    return p1+p2;
}




int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    int n;
    cin >> n;

    for (int i=1; i<=n; i++)
        cin >> arr[i];

    build_tree(1, 1, n);

    cerr << "--------------------------------" << endl;
    for (int i=1; i<n<<1; i++)
    {
        cerr << i << " vector -> ";
        for (auto it : tree[i].data)
            cerr << it << " ";
        cerr << endl;
    }
    cerr << "--------------------------------" << endl;

    int q;
    cin >> q;

    while (q--)
    {
        int x, y, k;
        cin >> x >> y >> k;

        cout << query_tree(1, 1, n, x, y, k) << endl;
    }
    return 0;
}









/****** Input Output    **********/
5
1 2 5 3 4
5
1 2 3
1 5 10
1 5 2
3 5 4
2 2 2

--------------------------------
1 vector -> 1 2 3 4 5
2 vector -> 1 2 5
3 vector -> 3 4
4 vector -> 1 2
5 vector -> 5
6 vector -> 3
7 vector -> 4
8 vector -> 1
9 vector -> 2
--------------------------------

2
5
1
1
0
/**********************************/