Merge Sort Tree Immutable

mergeSortTreeImmutable.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class MergeSortTreeImmutable {
    struct Node {
        vector<ll> v;
        pair<ll, ll> range;
        Node* left = nullptr;
        Node* right = nullptr;

        Node(ll l, ll r) {
            range = {l, r};
        }

        void push() {
            if(range.first == range.second) {
                return;
            }

            ll mid = (range.first + range.second) / 2;

            if (left == nullptr) {
                left = new Node(range.first, mid);
            }

            if (right == nullptr) {
                right = new Node(mid + 1, range.second);
            }
        }

        ll query(ll lb, ll rb) {
            ll l = lower_bound(v.begin(), v.end(), lb) - v.begin();
            ll r = upper_bound(v.begin(), v.end(), rb) - v.begin();

            return r - l;
        }
    };

    Node* root;

    void build(vector<ll>& v, Node* cur) {
        auto [l, r] = cur->range;

        if (l == r) {
            cur->v = {v[l]};
            return;
        }

        cur->push();

        build(v, cur->left);
        build(v, cur->right);

        cur->v = vector<ll>(r - l + 1);

        merge(cur->left->v.begin(), cur->left->v.end(), cur->right->v.begin(), cur->right->v.end(), cur->v.begin());
    }

    ll _query(Node* cur, ll start, ll end, ll lb, ll rb) {
        if(cur == nullptr) {
            return 0;
        }

        auto [l, r] = cur->range;

        if(r < start || l > end) {
            return 0;
        }

        if(start <= l && r <= end) {
            return cur->query(lb, rb);
        }

        return _query(cur->left, start, end, lb, rb) + _query(cur->right, start, end, lb, rb); 
    }

   public:
    MergeSortTreeImmutable(vector<ll>& v) {
        root = new Node(0, v.size() - 1);
        build(v, root);
    }

    ll query(ll l, ll r, ll lb, ll rb) { // count values in range [l, r] is in range [lb, rb]
        return _query(root, l, r, lb, rb);
    }
};

int main() {
    vector<ll> v = {1, 2, 3, 4, 5};
    MergeSortTreeImmutable tree(v);

    cout << tree.query(0, 4, 2, 3); // 2;
}