Ekan5h

from math import ceil, log2

class segment_tree:
    # merge(left, right): function used to merge the two halves
    # basef(value): function applied on individual values
    # basev: identity for merge function, merger(value, basev) = value
    # update(node_value, old, new): function to update the nodes
    def __init__(self, array, merge=lambda x,y:x+y, basef=lambda x:x, basev = 0):
        self.merge = merge
        self.basef = basef

Ekan5h

int rankUtil(node * head, T x, int r){
    if(head == NULL) return 0;
    T k = head->key;
    if(k == x) return r+1+head->nleft;
    if(k > x) return rankUtil(head->left, x, r);
    if(k < x) return rankUtil(head->right, x, r+head->nleft+1);
}

Ekan5h

T ksmallestUtil(node * head, int k){
    if(k<1 || k>n) return NULL;
    if(head->nleft == k-1) return head->key;
    if(head->nleft > k-1) return ksmallestUtil(head->left, k);
    return ksmallestUtil(head->right, k-1-head->nleft);
}

Ekan5h

node * removeUtil(node * head, T x, node * p){
            if(head == NULL) return NULL;
            if(x == head->key){
                node * l = head->left;
                node * r = head->right;
                while(p!=NULL){
                    if(x<p->key) p->nleft -= 1;
                    p=p->parent;
                }
                if(l == NULL){

Ekan5h

node * insertUtil(node * head, T x, node * p){
    if(head == NULL){
        n++;
        node * temp = new node(x,p);
        while(p!=NULL){
            if(x<p->key) p->nleft += 1;
            p=p->parent;
        }
        return temp;
    }

Ekan5h

template <typename T>
class AugBST{
    public:
        class node{
            public:
                T key;
                int nleft;
                node * left;
                node * right;
                node * parent;