Test (#4)

* update

* moved content in subdir

* rename file

* add test setup

* add test setup

* add github action

* automaticly test all cpp files

* timeout after 10s

* setulimit and dont zero memory

* test build pdf

* install latexmk

* update

* update

* ngerman

* fonts

* removed old code

* add first test

* added tests

* test in sorted order

* more tests

* simplified test

* more tests

* fix suffix tree

* fixes and improvements

* done ust lst directly

* fix swap

* add links to pdf

* fix constants

* add primorial

* add comment

* various improvements

* more tests

* added missing stuf

* more tests

* fix tests

* more tests

* more tests

* more tests

* fix recursion?

* test trie

* more tests

* only use python temporarily for listings

* only use python temporarily for listings

* more tests

* fix longestCommonSubstring

* more tests

* more tests

* made code more similiar

* fix?

* more tests

* more tests

* more tests

* add ahoCorasick test + limit 4GB stack size

* more tests

* fix test

* add additional test

* more tests

* more tests

* fix?

* better fix

* fix virtual tree

* more tests

* more tests

* recursive closest pair

* more tests

* decrease limit

* new tests

* more tests

* fix name

* more tests

* add test

* new test

* more tests

* more tests

* more tests

* more tests

* new test and content

* new code

* new code

* larger tests

* fix and test

* new test

* new test

* update pdf

* remove comments

* new test

* more tests

* more testcases

* more tests

* increased limit

* more tests

* more tests

* more tests

* new tests

* more tests

* shortened code

* new test

* add basic tests for bigint

* more tests

* removed old files

* new test

* ignore some files

* more auto more ccw

* fix test

* more tests

* fix

* new tests

* more tests

* more tests

* stronger test

* actually verify delaunay...

* more tests

* fix header

* more tests

* run tests parallel?

* test parralel?

* add --missing

* separate workflows

* test

* is the pdf checked?

* separate workflows

* fix workflow

* more workflows

---------

Co-authored-by: Yidi <noob999noob999@gmail.com>

1 files changed, 40 insertions, 0 deletions

diff --git a/content/datastructures/waveletTree.cpp b/content/datastructures/waveletTree.cpp
new file mode 100644
index 0000000..090cdb2
--- /dev/null
+++ b/content/datastructures/waveletTree.cpp
@@ -0,0 +1,40 @@
+struct WaveletTree {
+	using it = vector<ll>::iterator;
+	WaveletTree *ln = nullptr, *rn = nullptr;
+	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) {
+		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));
+		}
+		if (lo + 1 >= hi) return;
+		it pivot = stable_partition(from, to, f);
+		ln = new WaveletTree(from, pivot);
+		rn = new WaveletTree(pivot, to);
+	}
+
+	// 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;
+		int inLeft = b[r] - b[l];
+		if (k < inLeft) return ln->kth(b[l], b[r], k);
+		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;}
+};