fork download

copy

struct wavelet_tree{///1 indexed
    int low,high;
    wavelet_tree *lft=NULL,*rgt=NULL;
    int *pref=NULL;
	long long *sum=NULL;
 
    wavelet_tree(int *l, int *r, int low, int high):low(low),high(high){
        if(l>=r || low>=high)return;
        pref = new int[r-l+2];
		sum = new long long[r-l+2];
        pref[0]=0;
		sum[0]=0;
        int mid = (low+high)>>1, cnt=1;
        for(int *i=l; i!=r; i++,cnt++){
			pref[cnt] = pref[cnt-1]+((*i)<=mid);
			sum[cnt] = sum[cnt-1] + (*i);
		}
        int *pivot = stable_partition(l,r,[&](int x){return x<=mid;});
        lft = new wavelet_tree(l, pivot, low, mid);
        rgt = new wavelet_tree(pivot, r, mid+1, high);
    }
 
	long long sumQuery(int l, int r, int k){///Sum of elements less than 'k' in range [l,r]
		if(l>r || low>=k)return 0;
		if(low==high)return 1LL*(r-l+1)*low;
        if(high<k)return sum[r]-sum[l-1];
        return lft->sumQuery(pref[l-1]+1, pref[r], k) + rgt->sumQuery(l-pref[l-1], r-pref[r], k);
	}
 
    ~wavelet_tree(){
        if(pref!=NULL)delete []pref;
		if(sum!=NULL)delete []sum;
        if(lft!=NULL)delete lft;
        if(rgt!=NULL)delete rgt;
    }
};

prog.cpp:3:23: error: ‘NULL’ was not declared in this scope
     wavelet_tree *lft=NULL,*rgt=NULL;
                       ^~~~
prog.cpp:3:23: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp:1:1:
+#include <cstddef>
 struct wavelet_tree{///1 indexed
prog.cpp:3:23:
     wavelet_tree *lft=NULL,*rgt=NULL;
                       ^~~~
prog.cpp:3:33: error: ‘NULL’ was not declared in this scope
     wavelet_tree *lft=NULL,*rgt=NULL;
                                 ^~~~
prog.cpp:3:33: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp:4:15: error: ‘NULL’ was not declared in this scope
     int *pref=NULL;
               ^~~~
prog.cpp:4:15: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp:5:17: error: ‘NULL’ was not declared in this scope
  long long *sum=NULL;
                 ^~~~
prog.cpp:5:17: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp: In constructor ‘wavelet_tree::wavelet_tree(int*, int*, int, int)’:
prog.cpp:18:22: error: ‘stable_partition’ was not declared in this scope
         int *pivot = stable_partition(l,r,[&](int x){return x<=mid;});
                      ^~~~~~~~~~~~~~~~
prog.cpp: In destructor ‘wavelet_tree::~wavelet_tree()’:
prog.cpp:31:18: error: ‘NULL’ was not declared in this scope
         if(pref!=NULL)delete []pref;
                  ^~~~
prog.cpp:31:18: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp:32:11: error: ‘NULL’ was not declared in this scope
   if(sum!=NULL)delete []sum;
           ^~~~
prog.cpp:32:11: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp:33:17: error: ‘NULL’ was not declared in this scope
         if(lft!=NULL)delete lft;
                 ^~~~
prog.cpp:33:17: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp:34:17: error: ‘NULL’ was not declared in this scope
         if(rgt!=NULL)delete rgt;
                 ^~~~
prog.cpp:34:17: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?

Standard output is empty