diff options
Diffstat (limited to 'datastructures/waveletTree.cpp')
| -rw-r--r-- | datastructures/waveletTree.cpp | 16 |
1 files changed, 8 insertions, 8 deletions
diff --git a/datastructures/waveletTree.cpp b/datastructures/waveletTree.cpp index 4860a40..c211b0f 100644 --- a/datastructures/waveletTree.cpp +++ b/datastructures/waveletTree.cpp @@ -4,19 +4,19 @@ struct WaveletTree { vector<int> b = {0}; ll lo, hi; - WaveletTree(vector<ll> a) : WaveletTree(all(a), // call this - *min_element(all(a)), *max_element(all(a)) + 1) {} + WaveletTree(vector<ll> in) : WaveletTree(all(in)) {} - WaveletTree(it from, it to, ll x, ll y) : lo(x), hi(y) { - if (lo + 1 >= hi || from == to) return; + WaveletTree(it from, it to) : // call above one + lo(*min_element(from, to)), hi(*max_element(from, to) + 1) { + if (lo + 1 >= hi) return; ll mid = (lo + hi) / 2; auto f = [&](ll x){return x < mid;}; for (it c = from; c != to; c++) { b.push_back(b.back() + f(*c)); } it pivot = stable_partition(from, to, f); - ln = new WaveletTree(from, pivot, lo, mid); - rn = new WaveletTree(pivot, to, mid, hi); + ln = new WaveletTree(from, pivot); + rn = new WaveletTree(pivot, to); } // kth element in sort[l, r) all 0-indexed @@ -32,8 +32,8 @@ struct WaveletTree { int countSmaller(int l, int r, ll k) { if (l >= r || k <= lo) return 0; if (hi <= k) return r - l; - return ln->countSmaller(b[l], b[r], k) + - rn->countSmaller(l-b[l], r-b[r], k); + return ln->countSmaller(b[l], b[r], k) + + rn->countSmaller(l-b[l], r-b[r], k); } ~WaveletTree() {delete ln; delete rn;} |