Bit Manipulation

A complete Fenwick Tree implementation fits in fifteen lines of code, half the memory of a segment tree, and a smaller constant factor on every operation. The price of admission is that you only get prefix-style aggregates, but for the enormous class of problems that need exactly that, a **Fenwick Tree** (also called a Binary Indexed Tree, or BIT) is the right answer. This lesson covers the dynamic prefix-sum problem (static prefix sums are `O(1)` query and `O(n)` update; you want both in `O(log n)`), the `i & -i` lowbit trick that isolates the lowest set bit and implicitly defines which range each index covers, point update and prefix query in `O(log n)`, and the `prefix(R) - prefix(L-1)` identity that turns those into general range queries. You will also meet the difference-array technique that swaps the roles, supporting `O(log n)` range updates with `O(log n)` point queries. In **Arrays & Strings**, you saw how a flat array can encode rich structure when the indexing scheme is clever; the Fenwick tree pushes that idea further by letting binary representation itself carry the partition information. **Segment Tree** solved a more general version of this problem with explicit nodes; the BIT trades flexibility for simplicity and memory and wins on both metrics whenever prefix queries suffice. Next, **Sparse Table** addresses a different point in the trade space: arbitrary range minimum (and similar idempotent) queries, with `O(1)` queries when no updates are involved.

For a set of 32-bit integers, balanced BSTs answer successor and predecessor queries in `log_2(2^32) = 32` comparisons, and hash tables cannot answer those queries at all. A **Van Emde Boas (vEB) tree** answers them in `log_2(log_2(2^32)) = 5`, by recursively halving the bit-length of the universe at each level rather than halving the number of elements. That doubly-logarithmic bound is one of the most striking results in data structure theory. This lesson covers the recursive vEB structure (an integer universe `[0, u-1]` is split into `sqrt(u)` clusters of size `sqrt(u)` plus a summary structure over which clusters are non-empty, applied recursively), the explicit `min` and `max` fields that short-circuit the recursion to a single level when possible, the `O(log log u)` analysis for insert, delete, member, successor, predecessor, min, and max, and the `O(u)` space cost that makes vEB trees practical only for moderate universes. In **Binary Search Tree (BST)**, the height (and thus the operation cost) was governed by the number of stored keys; the vEB tree is governed instead by the size of the integer universe, a fundamentally different parameter. **Heaps & Priority Queue** introduced fast min and max access through a structural invariant; vEB trees push that idea further by also providing fast `successor` and `predecessor` over the same set. With Van Emde Boas, the data structures track is complete; the algorithms track is where these structures come alive in real problem solving.

Iterating over all subsets of every subset of an `n`-element set sounds like `4^n` work. The actual cost is `3^n`: each element is in three states (in the outer mask only, in both, or in neither), and the binomial theorem collapses the sum. Insights like that turn what looks like a complexity wall into a tight, elegant solution. **Advanced Bit Manipulation** collects those insights. You will generate Gray codes (adjacent values differ by one bit, used in error correction), enumerate all subsets of a bitmask via the `for (s = mask; s > 0; s = (s - 1) & mask)` template, and master bit tricks like isolating the lowest set bit with `x & -x`, turning it off with `x & (x - 1)`, counting trailing zeros, and swapping without a temp variable. The lesson also covers advanced XOR applications (range XOR, two missing numbers, XOR basis over GF(2)) and bitwise DP including profile DP for grid tiling. In **Bit Manipulation (Intro)**, you mastered the basic operators and the single-number XOR trick. This lesson treats bits as a full algorithmic medium. Next, **Complexity & Proof Intuition (Optional)** revisits the theoretical foundations behind everything built so far.

Given an array where every element appears twice except one, find the loner. The hash-map solution is `O(n)` time and `O(n)` space. XOR-ing every element together solves it in `O(n)` time and `O(1)` space, in three lines, exploiting the fact that `a ^ a = 0` and `a ^ 0 = a`. Knowing how integers are laid out as bits unlocks solutions like that across an entire family of problems. **Bit Manipulation (Intro)** covers the building blocks. You will master the six bitwise operators (`&`, `|`, `^`, `~`, `<<`, `>>`) and the standard tricks: check whether `n` is a power of two with `n & (n - 1) == 0`, count set bits, get/set/clear/toggle the ith bit, and the XOR "single number" pattern. The lesson then introduces bitmasks as compact set representations and previews how subset enumeration powers later bitmask DP and TSP algorithms. In **How to Read Code (JS & Python)**, you saw integers and arithmetic. This lesson zooms in past arithmetic: the same integer is also a fixed-width string of bits you can address one at a time. Next, **Divide and Conquer (Intro)** returns to recursion with the recurrence framework that explains merge and quick sort.