Ex - Manhattan Christmas Tree Editorial by cai_lw

Given an array of \(N\) integers in \([0,S)\), a wavelet tree can be constructed in \(O(N\log S)\) and answer online queries that count array elements satisfying \(i\in [l,r), a_i\in[d,u)\) in \(O(\log S)\), for any valid \(l, r, d, u\). This is sometimes called the range_freq operation of the wavelet tree.

Given a set of \(N\) points in 2D space, after some \(O(N\log N)\) pre-processing, the range_freq operation of the wavelet tree can be used to count points in any rectangular region in \(O(\log N)\). First, compress Y coordinates into integers in \([0,N)\), while maintaining their relative order. Then, sort points by their X coordinates, and create a wavelet tree from their Y coordinates. (Note that \(S=O(N)\) with the compressed Y coordinates) Finally, for a rectangular query, binary search the rectangle’s boundaries in the point set’s original X and Y coordinates, to find the corresponding \(l,r,d,u\) boundaries in the wavelet array.

Thus, for each query in this problem, one can binary search the answer by calling the rectangular point counting subroutine \(O(\log X)\) times. The overall time complexity is \(O(N\log N+Q\log N \log X)\).

AC submission (C++, 1563ms): https://atcoder.jp/contests/abc233/submissions/28146443

last update: