Skip to content

Wavelet Tree Hot Sheet

Use this page when one static array gets many subarray queries whose answer depends on value order inside the range:

  • k-th smallest
  • count <= x
  • count == x

Do Not Use When

Choose By Signal

Core Invariants

  • each node owns one compressed value interval [lo, hi]
  • each node stores the subsequence of array elements whose values lie in that interval, with original order preserved
  • pref[i] means: among the first i subsequence elements at this node, how many go to the left child
  • for a node-local query interval [l, r), the child ranges become:
  • left -> [pref[l], pref[r))
  • right -> [l - pref[l], r - pref[r))

Main Query Rules

  • kth_smallest: compute how many queried elements go left; go left if k < left_count, otherwise go right with k -= left_count
  • count_leq(x): prune whole value intervals that are fully above or fully below x
  • count_equal(x): follow only the unique leaf path for x

Main Traps

  • mixing original-array positions with node-local subsequence positions after the first descent
  • forgetting to convert statement k from one-based to zero-based
  • skipping coordinate compression when values are large
  • stretching the starter to dynamic updates or wavelet-matrix-only variants

Exact Starter In This Repo

Reopen Paths