4

Wavlet Tree                                                  |
                                                             |
struct WAVELET_TREE {                                        |      // count nos in [l, r] equal to k
	int lo, hi;                                              |      int COUNT_EQUAL(int l, int r, int k) {
	WAVELET_TREE *l, *r;                                     |      	if (l > r or k < lo or k > hi)
    vector <int> b;                                          |      		return 0;
	// nos are in range [x, y]                               |     		if (lo == hi)
    // array indices are [from, to]                          |      		return (r - l + 1);
    WAVELET_TREE(int *from, int *to, int x, int y) {         |      	int lb = b[l-1], rb = b[r], mid = (lo + hi) >> 1;
		lo = x; hi = y;                                      |          if (k <= mid)
		if (lo == hi or from >= to)                          |          	return this->l->COUNT_EQUAL(lb+1, rb, k);
			return;                                          |          else
		int mid = (x + y) >> 1;                              |              return this->r->COUNT_EQUAL(l-lb, r-rb, k);
		auto f = [mid](int x) {                              |      }
			return x <= mid;                                 |
		};                                                   |      ~WAVELET_TREE() {
		b.reserve(to - from + 1);                            |      	delete l;
		b.push_back(0);  // make it 1 indexed                |          delete r;
		for (auto it = from; it != to; it++)                 |      }
			b.push_back(b.back() + f(*it));                  |   };
		auto pivot = stable_partition(from, to, f);          |
		l = new WAVELET_TREE(from, pivot, lo, mid);          |
		r = new WAVELET_TREE(pivot, to, mid + 1, hi);        | Call :
	}                                                        |       WAVELET_TREE *T;
	// k'th smallest element in[l,r]                         |       T = new WAVELET_TREE(arr+1, arr+N+1, 1, MAXN)
	int KTH(int l, int r, int k) {                           |
		if (l > r)	    return 0;                            |       MAXN = max number of the set
		if (lo == hi)	return lo;                           |              Don't use negetive number
		int lb = b[l-1], rb = b[r], inLeft = rb - lb;        |
		if (inLeft <= k)                                     |
			return this->l->KTH(lb+1, rb, k);                |       Complexity : nlogn
		else                                                 |       QUERY      : logn
		    return this->r->KTH(l-lb, r-rb, k-inLeft);       |
	}                                                        |
	// count nos in [l, r] less than or equal to k           |
	int LTE(int l, int r, int k) {                           |
		if (l > r or k < lo)                                 |
			return 0;                                        |
		if (lo == hi)                                        |
			return (r - l + 1);                              |
		int lb = b[l-1], rb = b[r];                          |
		int total = this->l->LTE(lb+1, rb, k) +              |
                    this->r->LTE(l-lb, r-rb, k);             |
	}