Advanced Trees and Specialized Structures

For each, explain the query/update it is designed to optimize and its memory/complexity trade-offs.

KD-tree and spatial queries.

Quadtrees and octrees.

Link-cut tree overview.

Euler-tour trees overview.

Rope for large editable strings.

Suffix array and suffix tree.

Wavelet tree/matrix.

Treap and implicit treap.

Bloom filter and probabilistic membership structures.

Cuckoo filter overview.

rank / k-th element with updates augment a balanced BST with sizes all intervals overlapping a point or interval O(log n + k) stores max endpoint per subtree orthogonal range counting in 2-D O(log² n + k) O(n log n) memory nearest neighbour, range search in low dimensions

O(log n) typical, O(√n) worst for 2-D range degrades in high dimensions Quadtree / octree spatial subdivision of 2-D / 3-D space depends on data uneven data makes deep trees heap on values, BST on positions; RMQ ↔ LCA O(n) build with a stack Link-cut / Euler-tour trees dynamic forests: link, cut, path/subtree queries O(log n) amortized insert/delete in long strings slower indexing than an array k-th smallest / rank in a range array with split/merge, reverse ranges O(log n) expected ordered set with simple concurrent variants extra pointers per level

“definitely absent / maybe present” membership false positives, no deletion like Bloom, with deletion can fail to insert when very full

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

The Bloom filter has no false negatives by construction; its false-positive rate follows (1 − e^(−kn/m))^k closely, as the run shows. The skip list's search takes about one forward step per level in expectation, so about log₂ n forward steps in total — the run measured 15.2 for n = 100 000 (log₂ 100 000 ≈ 16.6).

#include <bits/stdc++.h>
using namespace std;

// Bloom filter: m bits, k hash functions derived from two base hashes (Kirsch-Mitzenmacher)
struct Bloom {
    vector<bool> bits; int k;
    Bloom(size_t m, int k_) : bits(m), k(k_) {}
    pair<uint64_t, uint64_t> h(uint64_t x) const {
        uint64_t a = x * 0x9E3779B97F4A7C15ULL; a ^= a >> 31;
        uint64_t b = (x ^ 0xC2B2AE3D27D4EB4FULL) * 0xBF58476D1CE4E5B9ULL; b ^= b >> 29;
        return {a, b | 1};
    }
    void add(uint64_t x) { auto [a, b] = h(x); for (int i = 0; i < k; ++i) bits[(a + i * b) % bits.size()] = true; }
    bool mayContain(uint64_t x) const { auto [a, b] = h(x); for (int i = 0; i < k; ++i) if (!bits[(a + i * b) % bits.size()]) return false; return true; }
};

// skip list with expected O(log n) search
struct SkipList {
    static const int MAXL = 20;
    struct N { int key; vector<N*> next; N(int k, int l) : key(k), next(l, nullptr) {} };
    N head{INT_MIN, MAXL}; mt19937 rng{99}; int level = 1;
    ~SkipList() { N* x = head.next[0]; while (x) { N* nx = x->next[0]; delete x; x = nx; } }
    int randomLevel() { int l = 1; while (l < MAXL && rng() % 2) ++l; return l; }
    void insert(int key) {
        vecto
…

Bloom filter: false negatives 0, false positive rate 0.0097 (theory 0.0100)
skip list: 1000/1000 found, levels 16, average forward steps 15.2 for n = 100000

Quiz

? A Bloom filter answers “maybe present” for a key. What do you know?
+ The key might be present; a false positive is possible. :: “Definitely absent” is the only certain answer.
- The key is present. :: False positives exist.
- The key is absent. :: That is the other answer.
- The filter is full. :: No.

? Which structure stores both a BST order on positions and a heap order on values?
+ Cartesian tree :: Used to reduce RMQ to LCA.
- Skip list :: Probabilistic levels.
- B-tree :: Multiway search tree.
- Bloom filter :: Bit array.

? Which structures are randomised? (select all that apply)
+ Skip list :: Random levels.
+ Treap :: Random priorities.
- Sparse table :: Deterministic.
+ Bloom filter (via its hash functions) :: Its errors depend on hashing.