summaryrefslogtreecommitdiff
path: root/content/datastructures
diff options
context:
space:
mode:
Diffstat (limited to 'content/datastructures')
-rw-r--r--content/datastructures/datastructures.tex57
-rw-r--r--content/datastructures/dynamicConvexHull.cpp10
-rw-r--r--content/datastructures/fenwickTree.cpp4
-rw-r--r--content/datastructures/fenwickTree2.cpp16
-rw-r--r--content/datastructures/lazyPropagation.cpp23
-rw-r--r--content/datastructures/monotonicConvexHull.cpp43
-rw-r--r--content/datastructures/pbds.cpp16
-rw-r--r--content/datastructures/segmentTree.cpp9
-rw-r--r--content/datastructures/sparseTable.cpp6
-rw-r--r--content/datastructures/sparseTableDisjoint.cpp10
-rw-r--r--content/datastructures/stlHashMap.cpp17
-rw-r--r--content/datastructures/stlPriorityQueue.cpp8
-rw-r--r--content/datastructures/stlTree.cpp13
-rw-r--r--content/datastructures/treap2.cpp10
-rw-r--r--content/datastructures/waveletTree.cpp26
15 files changed, 125 insertions, 143 deletions
diff --git a/content/datastructures/datastructures.tex b/content/datastructures/datastructures.tex
index 40132a9..a0eea64 100644
--- a/content/datastructures/datastructures.tex
+++ b/content/datastructures/datastructures.tex
@@ -10,7 +10,7 @@
\subsubsection{Lazy Propagation}
Assignment modifications, sum queries \\
- \method{lower\_bound}{erster Index in $[l, r)$ $\geq$ x (erfordert max-combine)}{\log(n)}
+ \method{lower\_bound}{erster Index in $[l, r)$ $\geq x$ (erfordert max-combine)}{\log(n)}
\sourcecode{datastructures/lazyPropagation.cpp}
\end{algorithm}
@@ -20,6 +20,8 @@
\method{kth}{sort $[l, r)[k]$}{\log(\Sigma)}
\method{countSmaller}{Anzahl elemente in $[l, r)$ kleiner als $k$}{\log(\Sigma)}
\end{methods}
+ $\Sigma$ ist die Gr\"o\ss e des Eingabebereichs, d.h.
+ $\mathit{max} - \mathit{min}$.
\sourcecode{datastructures/waveletTree.cpp}
\end{algorithm}
\columnbreak
@@ -27,15 +29,15 @@
\begin{algorithm}{Fenwick Tree}
\begin{methods}
\method{init}{baut den Baum auf}{n\*\log(n)}
- \method{prefix\_sum}{summe von $[0, i]$}{\log(n)}
+ \method{prefix\_sum}{summe von $[0, i)$}{\log(n)}
\method{update}{addiert ein Delta zu einem Element}{\log(n)}
\end{methods}
\sourcecode{datastructures/fenwickTree.cpp}
\begin{methods}
\method{init}{baut den Baum auf}{n\*\log(n)}
- \method{prefix\_sum}{summe von [$0, i]$}{\log(n)}
- \method{update}{addiert ein Delta zu allen Elementen $[l, r)$. $l\leq r$!}{\log(n)}
+ \method{prefix\_sum}{summe von $[0, i)$}{\log(n)}
+ \method{update}{addiert ein Delta zu allen Elementen $[l, r)$}{\log(n)}
\end{methods}
\sourcecode{datastructures/fenwickTree2.cpp}
\end{algorithm}
@@ -56,7 +58,7 @@
\begin{algorithm}{Range Minimum Query}
\begin{methods}
\method{init}{baut Struktur auf}{n\*\log(n)}
- \method{queryIdempotent}{Index des Minimums in $[l, r)$. $l<r$!}{1}
+ \method{queryIdempotent}{Index des Minimums in $[l, r)$}{1}
\end{methods}
\begin{itemize}
\item \code{better}-Funktion muss idempotent sein!
@@ -64,6 +66,14 @@
\sourcecode{datastructures/sparseTable.cpp}
\end{algorithm}
+\begin{algorithm}[optional]{Range Aggregate Query}
+ \begin{methods}
+ \method{init}{baut Struktur auf}{n\*\log(n)}
+ \method{query}{Aggregat über $[l,r)$}{1}
+ \end{methods}
+ \sourcecode{datastructures/sparseTableDisjoint.cpp}
+\end{algorithm}
+
\begin{algorithm}{STL-Bitset}
\sourcecode{datastructures/bitset.cpp}
\end{algorithm}
@@ -80,30 +90,43 @@
\end{methods}
\sourcecode{datastructures/LCT.cpp}
\end{algorithm}
-\clearpage
+\columnbreak
-\begin{algorithm}{Lichao}
- \sourcecode{datastructures/lichao.cpp}
+\begin{algorithm}{Lower Envelope (Convex Hull Optimization)}
+ Um aus einem Lower Envelope einen Upper Envelope zu machen (oder
+ umgekehrt), einfach beim Einfügen der Geraden $m$ und $b$ negieren.
+ \subsubsection{Monotonic}
+ \begin{methods}
+ \method{add}{add line $mx + b$, $m$ is decreasing}{1}
+ \method{query}{minimum value at $x$, $x$ is increasing}{1}
+ \end{methods}
+ \sourcecode{datastructures/monotonicConvexHull.cpp}
+ \subsubsection{Dynamic}
+ \begin{methods}
+ \method{add}{add line $mx + b$}{\log(n)}
+ \method{query}{minimum value at $x$}{\log(n)}
+ \end{methods}
+ \sourcecode{datastructures/dynamicConvexHull.cpp}
+ \subsubsection{Li Chao Tree}
+ Every pair of functions has at most one intersection.
+
+ \begin{methods}
+ \method{insert}{add function}{\log(|xs|)}
+ \method{query}{minimum value at $x$, $x \in xs$}{\log(|xs|)}
+ \end{methods}
+ \sourcecode{datastructures/lichao.cpp}
\end{algorithm}
\begin{algorithm}{Policy Based Data Structures}
- \textbf{Wichtig:} Verwende \code{p.swap(p2)} anstatt \code{swap(p, p2)}!
- \sourcecode{datastructures/stlPriorityQueue.cpp}
- \columnbreak
\sourcecode{datastructures/pbds.cpp}
\end{algorithm}
-\begin{algorithm}{Lower/Upper Envelope (Convex Hull Optimization)}
- Um aus einem lower envelope einen upper envelope zu machen (oder umgekehrt), einfach beim Einfügen der Geraden $m$ und $b$ negieren.
- \sourcecode{datastructures/monotonicConvexHull.cpp}
- \sourcecode{datastructures/dynamicConvexHull.cpp}
-\end{algorithm}
-
\begin{algorithm}{Union-Find}
\begin{methods}
\method{init}{legt $n$ einzelne Unions an}{n}
\method{findSet}{findet den Repräsentanten}{\log(n)}
\method{unionSets}{vereint 2 Mengen}{\log(n)}
+ \method{size}{zählt Elemente in Menge, die $a$ enthält}{\log(n)}
\method{m\*findSet + n\*unionSets}{Folge von Befehlen}{n+m\*\alpha(n)}
\end{methods}
\sourcecode{datastructures/unionFind.cpp}
diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp
index d669847..2bd67a6 100644
--- a/content/datastructures/dynamicConvexHull.cpp
+++ b/content/datastructures/dynamicConvexHull.cpp
@@ -19,13 +19,11 @@ struct HullDynamic : multiset<Line, less<>> {
auto x = insert({m, b, 0});
while (isect(x, next(x))) erase(next(x));
if (x != begin()) {
- x--;
- if (isect(x, next(x))) {
- erase(next(x));
- isect(x, next(x));
- }}
+ --x;
+ while (isect(x, next(x))) erase(next(x));
+ }
while (x != begin() && prev(x)->p >= x->p) {
- x--;
+ --x;
isect(x, erase(next(x)));
}}
diff --git a/content/datastructures/fenwickTree.cpp b/content/datastructures/fenwickTree.cpp
index eb5cd73..7013613 100644
--- a/content/datastructures/fenwickTree.cpp
+++ b/content/datastructures/fenwickTree.cpp
@@ -1,7 +1,7 @@
vector<ll> tree;
void update(int i, ll val) {
- for (i++; i < sz(tree); i += i & -i) tree[i] += val;
+ for (i++; i < ssize(tree); i += i & -i) tree[i] += val;
}
void init(int n) {
@@ -10,6 +10,6 @@ void init(int n) {
ll prefix_sum(int i) {
ll sum = 0;
- for (i++; i > 0; i -= i & -i) sum += tree[i];
+ for (; i > 0; i &= i-1) sum += tree[i];
return sum;
}
diff --git a/content/datastructures/fenwickTree2.cpp b/content/datastructures/fenwickTree2.cpp
index 9384e3c..7fcdbb9 100644
--- a/content/datastructures/fenwickTree2.cpp
+++ b/content/datastructures/fenwickTree2.cpp
@@ -1,21 +1,21 @@
vector<ll> add, mul;
void update(int l, int r, ll val) {
- for (int tl = l + 1; tl < sz(add); tl += tl & -tl)
+ for (int tl = l + 1; tl < ssize(add); tl += tl & -tl)
add[tl] += val, mul[tl] -= val * l;
- for (int tr = r + 1; tr < sz(add); tr += tr & -tr)
+ for (int tr = r + 1; tr < ssize(add); tr += tr & -tr)
add[tr] -= val, mul[tr] += val * r;
}
-void init(vector<ll>& v) {
- mul.assign(sz(v) + 1, 0);
- add.assign(sz(v) + 1, 0);
- for(int i = 0; i < sz(v); i++) update(i, i + 1, v[i]);
+void init(vector<ll> &v) {
+ mul.assign(size(v) + 1, 0);
+ add.assign(size(v) + 1, 0);
+ for(int i = 0; i < ssize(v); i++) update(i, i + 1, v[i]);
}
ll prefix_sum(int i) {
- ll res = 0; i++;
- for (int ti = i; ti > 0; ti -= ti & -ti)
+ ll res = 0;
+ for (int ti = i; ti > 0; ti &= ti-1)
res += add[ti] * i + mul[ti];
return res;
}
diff --git a/content/datastructures/lazyPropagation.cpp b/content/datastructures/lazyPropagation.cpp
index 441590e..82176cb 100644
--- a/content/datastructures/lazyPropagation.cpp
+++ b/content/datastructures/lazyPropagation.cpp
@@ -1,23 +1,22 @@
struct SegTree {
using T = ll; using U = ll;
- int n;
static constexpr T E = 0; // Neutral element for combine
- static constexpr U UF = inf; // Unused value by updates
- vector<T> tree;
+ static constexpr U UF = 1e18; // Unused value by updates
+ int n;
+ vector<T> tree; vector<U> lazy;
int h;
- vector<U> lazy;
- vector<int> k; // size of segments (optional)
+ vector<ll> k; // size of segments (optional)
- SegTree(const vector<T>& a) : n(sz(a) + 1), tree(2 * n, E),
+ SegTree(const vector<T>& a) : n(ssize(a) + 1), tree(2 * n, E),
//SegTree(int size, T def = E) : n(size + 1), tree(2 * n, def),
- h(__lg(2 * n)), lazy(n, UF), k(2 * n, 1) {
- copy(all(a), tree.begin() + n);
+ lazy(n, UF), h(__lg(2 * n)), k(2 * n, 1) {
+ ranges::copy(a, tree.begin() + n);
for (int i = n - 1; i > 0; i--) {
k[i] = 2 * k[2 * i];
tree[i] = comb(tree[2 * i], tree[2 * i + 1]);
}}
- T comb(T a, T b) {return a + b;} // Modify this + E
+ T comb(T a, T b) { return a + b; } // Modify this + E
void apply(int i, U val) { // And this + UF
tree[i] = val * k[i];
@@ -44,17 +43,17 @@ struct SegTree {
void update(int l, int r, U val) {
l += n, r += n;
int l0 = l, r0 = r;
- push(l0), push(r0 - 1);
+ push(l0), push(r0);
for (; l < r; l /= 2, r /= 2) {
if (l&1) apply(l++, val);
if (r&1) apply(--r, val);
}
- build(l0), build(r0 - 1);
+ build(l0), build(r0);
}
T query(int l, int r) {
l += n, r += n;
- push(l), push(r - 1);
+ push(l), push(r);
T resL = E, resR = E;
for (; l < r; l /= 2, r /= 2) {
if (l&1) resL = comb(resL, tree[l++]);
diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp
index 44bff83..e7b9b3e 100644
--- a/content/datastructures/monotonicConvexHull.cpp
+++ b/content/datastructures/monotonicConvexHull.cpp
@@ -1,27 +1,26 @@
-// Lower Envelope mit MONOTONEN Inserts und Queries. Jede neue
-// Gerade hat kleinere Steigung als alle vorherigen.
-struct Line {
- ll m, b;
- ll operator()(ll x) {return m*x+b;}
-};
+struct Envelope {
+ struct Line {
+ ll m, b;
+ ll operator()(ll x) { return m*x+b; }
+ };
-vector<Line> ls;
-int ptr = 0;
+ vector<Line> ls;
+ int ptr = 0;
-bool bad(Line l1, Line l2, Line l3) {
- return (l3.b-l1.b)*(l1.m-l2.m) < (l2.b-l1.b)*(l1.m-l3.m);
-}
+ static bool bad(Line l1, Line l2, Line l3) {
+ return (l3.b-l1.b)*(l1.m-l2.m) < (l2.b-l1.b)*(l1.m-l3.m);
+ }
-void add(ll m, ll b) { // Laufzeit O(1) amortisiert
- while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, b})) {
- ls.pop_back();
+ void add(ll m, ll b) {
+ while (sz(ls) > 1 && bad(ls.end()[-2], ls.back(), {m, b})) {
+ ls.pop_back();
+ }
+ ls.push_back({m, b});
+ ptr = min(ptr, sz(ls) - 1);
}
- ls.push_back({m, b});
- ptr = min(ptr, sz(ls) - 1);
-}
-ll query(ll x) { // Laufzeit: O(1) amortisiert
- ptr = min(ptr, sz(ls) - 1);
- while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++;
- return ls[ptr](x);
-} \ No newline at end of file
+ ll query(ll x) {
+ while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++;
+ return ls[ptr](x);
+ }
+};
diff --git a/content/datastructures/pbds.cpp b/content/datastructures/pbds.cpp
index f0889a2..d00b635 100644
--- a/content/datastructures/pbds.cpp
+++ b/content/datastructures/pbds.cpp
@@ -1,13 +1,21 @@
+#include <ext/pb_ds/priority_queue.hpp>
+template<typename T>
+using pQueue = __gnu_pbds::priority_queue<T>; //<T, greater<T>>
+auto it = pq.push(5); // O(1)
+pq.modify(it, 6); // O(log n)
+pq.erase(it); // O(log n)
+pq.join(pq2); // O(1)
+pq.swap(pq2); // O(1)
+
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag,
tree_order_statistics_node_update>;
-// T.order_of_key(x): number of elements strictly less than x
-// *T.find_by_order(k): k-th element
+T.order_of_key(x); // number of elements strictly less than x
+auto it = T.find_by_order(k); // k-th element
-template<typename T>
-struct chash {
+template<typename T> struct chash {
static const uint64_t C = ll(2e18 * acos(-1)) | 199; // random odd
size_t operator()(T o) const {
return __builtin_bswap64(hash<T>()(o) * C);
diff --git a/content/datastructures/segmentTree.cpp b/content/datastructures/segmentTree.cpp
index 6b69d0b..1fbf886 100644
--- a/content/datastructures/segmentTree.cpp
+++ b/content/datastructures/segmentTree.cpp
@@ -4,14 +4,15 @@ struct SegTree {
vector<T> tree;
static constexpr T E = 0; // Neutral element for combine
- SegTree(vector<T>& a) : n(sz(a)), tree(2 * n) {
- //SegTree(int size, T val = E) : n(size), tree(2 * n, val) {
- copy(all(a), tree.begin() + n);
+ SegTree(vector<T>& a) : n(ssize(a)), tree(2 * n, E) {
+ ranges::copy(a, tree.begin() + n);
+ //SegTree(int size, T val = E) : n(size), tree(2 * n, E) {
+ // fill(tree.begin() + n, tree.end(), val);
for (int i = n - 1; i > 0; i--) { // remove for range update
tree[i] = comb(tree[2 * i], tree[2 * i + 1]);
}}
- T comb(T a, T b) {return a + b;} // modify this + neutral
+ T comb(T a, T b) { return a + b; } // modify this + neutral
void update(int i, T val) {
tree[i += n] = val; // apply update code
diff --git a/content/datastructures/sparseTable.cpp b/content/datastructures/sparseTable.cpp
index b3f946e..5e84236 100644
--- a/content/datastructures/sparseTable.cpp
+++ b/content/datastructures/sparseTable.cpp
@@ -6,9 +6,9 @@ struct SparseTable {
return a[lidx] <= a[ridx] ? lidx : ridx;
}
- void init(vector<ll>* vec) {
- int n = sz(*vec);
- a = vec->data();
+ void init(vector<ll> &vec) {
+ int n = sz(vec);
+ a = vec.data();
st.assign(__lg(n) + 1, vector<int>(n));
iota(all(st[0]), 0);
for (int j = 0; (2 << j) <= n; j++) {
diff --git a/content/datastructures/sparseTableDisjoint.cpp b/content/datastructures/sparseTableDisjoint.cpp
index 55165d4..39c7caa 100644
--- a/content/datastructures/sparseTableDisjoint.cpp
+++ b/content/datastructures/sparseTableDisjoint.cpp
@@ -7,16 +7,16 @@ struct DisjointST {
return x + y;
}
- void init(vector<ll>* vec) {
- int n = sz(*vec);
- a = vec->data();
+ void init(vector<ll> &vec) {
+ int n = sz(vec);
+ a = vec.data();
dst.assign(__lg(n) + 1, vector<ll>(n + 1, neutral));
for (int h = 0, l = 1; l <= n; h++, l *= 2) {
for (int c = l; c < n + l; c += 2 * l) {
for (int i = c; i < min(n, c + l); i++)
- dst[h][i + 1] = combine(dst[h][i], vec->at(i));
+ dst[h][i + 1] = combine(dst[h][i], vec[i]);
for (int i = min(n, c); i > c - l; i--)
- dst[h][i - 1] = combine(vec->at(i - 1), dst[h][i]);
+ dst[h][i - 1] = combine(vec[i - 1], dst[h][i]);
}}}
ll query(int l, int r) {
diff --git a/content/datastructures/stlHashMap.cpp b/content/datastructures/stlHashMap.cpp
deleted file mode 100644
index b107dde..0000000
--- a/content/datastructures/stlHashMap.cpp
+++ /dev/null
@@ -1,17 +0,0 @@
-#include <ext/pb_ds/assoc_container.hpp>
-using namespace __gnu_pbds;
-
-template<typename T>
-struct betterHash {
- size_t operator()(T o) const {
- size_t h = hash<T>()(o) ^ 42394245; //random value
- h = ((h >> 16) ^ h) * 0x45d9f3b;
- h = ((h >> 16) ^ h) * 0x45d9f3b;
- h = ((h >> 16) ^ h);
- return h;
-}};
-
-template<typename K, typename V, typename H = betterHash<K>>
-using hashMap = gp_hash_table<K, V, H>;
-template<typename K, typename H = betterHash<K>>
-using hashSet = gp_hash_table<K, null_type, H>;
diff --git a/content/datastructures/stlPriorityQueue.cpp b/content/datastructures/stlPriorityQueue.cpp
deleted file mode 100644
index 32b2455..0000000
--- a/content/datastructures/stlPriorityQueue.cpp
+++ /dev/null
@@ -1,8 +0,0 @@
-#include <ext/pb_ds/priority_queue.hpp>
-template<typename T>
-using pQueue = __gnu_pbds::priority_queue<T>; //<T, greater<T>>
-
-auto it = pq.push(5);
-pq.modify(it, 6);
-pq.join(pq2);
-// push, join are O(1), pop, modify, erase O(log n) amortized
diff --git a/content/datastructures/stlTree.cpp b/content/datastructures/stlTree.cpp
deleted file mode 100644
index fbb68b9..0000000
--- a/content/datastructures/stlTree.cpp
+++ /dev/null
@@ -1,13 +0,0 @@
-#include <ext/pb_ds/assoc_container.hpp>
-#include <ext/pb_ds/tree_policy.hpp>
-using namespace std; using namespace __gnu_pbds;
-template<typename T>
-using Tree = tree<T, null_type, less<T>, rb_tree_tag,
- tree_order_statistics_node_update>;
-
-int main() {
- Tree<int> X;
- for (int i : {1, 2, 4, 8, 16}) X.insert(i);
- *X.find_by_order(3); // => 8
- X.order_of_key(10); // => 4 = min i, mit X[i] >= 10
-}
diff --git a/content/datastructures/treap2.cpp b/content/datastructures/treap2.cpp
index c5a60e9..e40da0d 100644
--- a/content/datastructures/treap2.cpp
+++ b/content/datastructures/treap2.cpp
@@ -3,7 +3,7 @@ struct Treap {
struct Node {
ll val;
int prio, size = 1, l = -1, r = -1;
- Node(ll x) : val(x), prio(rng()) {}
+ Node(ll x): val(x), prio(rng()) {}
};
vector<Node> treap;
@@ -15,14 +15,14 @@ struct Treap {
void upd(int v) {
if (v < 0) return;
- auto& V = treap[v];
+ auto &V = treap[v];
V.size = 1 + getSize(V.l) + getSize(V.r);
// Update Node Code
}
void push(int v) {
if (v < 0) return;
- //auto& V = treap[v];
+ //auto &V = treap[v];
//if (V.lazy) {
// Lazy Propagation Code
// if (V.l >= 0) treap[V.l].lazy = true;
@@ -33,7 +33,7 @@ struct Treap {
pair<int, int> split(int v, int k) {
if (v < 0) return {-1, -1};
- auto& V = treap[v];
+ auto &V = treap[v];
push(v);
if (getSize(V.l) >= k) { // "V.val >= k" for lower_bound(k)
auto [left, right] = split(V.l, k);
@@ -66,7 +66,7 @@ struct Treap {
void insert(int i, ll val) { // and i = val
auto [left, right] = split(root, i);
treap.emplace_back(val);
- left = merge(left, sz(treap) - 1);
+ left = merge(left, ssize(treap) - 1);
root = merge(left, right);
}
diff --git a/content/datastructures/waveletTree.cpp b/content/datastructures/waveletTree.cpp
index 090cdb2..55167b6 100644
--- a/content/datastructures/waveletTree.cpp
+++ b/content/datastructures/waveletTree.cpp
@@ -1,25 +1,20 @@
struct WaveletTree {
- using it = vector<ll>::iterator;
- WaveletTree *ln = nullptr, *rn = nullptr;
+ unique_ptr<WaveletTree> ln, rn;
vector<int> b = {0};
ll lo, hi;
- WaveletTree(vector<ll> in) : WaveletTree(all(in)) {}
-
- WaveletTree(it from, it to) : // call above one
- lo(*min_element(from, to)), hi(*max_element(from, to) + 1) {
+ WaveletTree(auto in) : lo(*ranges::min_element(in)),
+ hi(*ranges::max_element(in) + 1) {
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));
- }
+ auto f = [&](ll x) { return x < mid; };
+ for (ll x: in) b.push_back(b.back() + f(x));
if (lo + 1 >= hi) return;
- it pivot = stable_partition(from, to, f);
- ln = new WaveletTree(from, pivot);
- rn = new WaveletTree(pivot, to);
+ auto right = ranges::stable_partition(in, f);
+ ln = make_unique<WaveletTree>(
+ ranges::subrange(begin(in), begin(right)));
+ rn = make_unique<WaveletTree>(right);
}
- // kth element in sort[l, r) all 0-indexed
ll kth(int l, int r, int k) {
if (k < 0 || l + k >= r) return -1;
if (lo + 1 >= hi) return lo;
@@ -28,13 +23,10 @@ struct WaveletTree {
else return rn->kth(l-b[l], r-b[r], k-inLeft);
}
- // count elements in[l, r) smaller than k
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);
}
-
- ~WaveletTree() {delete ln; delete rn;}
};
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 20:22:51 +0000