Data Structures19 sections · 729 units
Open in Course

Common Bugs

Debugging wavelet trees

Bug 1: Off-by-one in rank rank(B,i)\text{rank}(B, i) counts bits in [0,i)[0, i) not [0,i][0, i].

Use rank(B,r+1)−rank(B,l)\text{rank}(B, r+1) - \text{rank}(B, l) for range [l,r][l, r]. Bug 2: Wrong child selection For value vv with mid=(lo+hi)/2\text{mid} = (\text{lo} + \text{hi}) / 2:

  • v≤midv \leq \text{mid}: go left
  • v>midv > \text{mid}: go right

Bug 3: Forgetting coordinate compression If values exceed 10610^6, wavelet tree depth becomes problematic.

Always compress. Bug 4: Integer overflow in mid Use lo+(hi−lo)/2\text{lo} + (\text{hi} - \text{lo}) / 2 not (lo+hi)/2(\text{lo} + \text{hi}) / 2 to avoid overflow with 32-bit integers.