Implicit segment tree

/*
Implicit segment tree

Requires O(Nlog(val)) memory
*/

#include <bits/stdc++.h>
#define mid (left+(right-left)/2)
using namespace std;

struct Node
{
    int val;
    Node *l, *r;
};

void update (Node *v, int left, int right, int x, int val)
{
    if (left==right)
    {
        v->val=val;
        return;
    }

    if (x<=mid)
    {
        if (v->l==NULL) v->l=new Node();
        update (v->l, left, mid, x, val);
        v->val+=(v->l)->val;
    }
    else
    {
        if (v->r==NULL) v->r=new Node();
        update (v->r, mid+1, right, x, val);
        v->val+=(v->r)->val;
    }
}

int query (Node *v, int left, int right, int l, int r)
{
    if (l<=left && right<=r) return v->val;

    int ret=0;
    if (l<=mid)
    {
        if (v->l==NULL) return 0;
        return query(v->l, left, mid, l, r);
    }
    if (r>mid)
    {
        if (v->r==NULL) return 0;
        return query(v->r, mid+1, right, l, r);
    }
}

int main()
{
    int N=1e9;

    Node *root=new Node();

    update (root, 1, N, (int)1e7, (int)1e7);

    cout << query(root, 1, N, 1, N);

    return 0;
}