公式解説 の内容 (merge-sort tree) を前提に、Fractional Cascading を用いることで時間計算量を \(O((N + Q)\log N)\) に改善します。ngtkana さんのユーザ解説 で言及されていたので書きました。筆者は ei1333 さんの記事 で Fractional Cascading を勉強しました。

公式解説の方法でクエリ \(O(\log^2 N)\) 時間となっていたのは、\(O(\log N)\) 個ある各ノードについて毎回二分探索を行っていたためです。ここで、セグメント木の（再帰による）トップダウンな実装のほうを考えることにして、ノードを降りる際、降りた先での二分探索の結果を同時に得られるようにすることを考えます。これは、ボトムアップに木を構築する際の列のマージと同時に前計算しておくことができます。これにより、二分探索は根ノードについての \(1\) 回のみを行えばよくなるので、クエリ \(O(\log N)\) 時間に改善されます。データ構造の構築は変わらず \(O(N\log N)\) 時間で、空間計算量は \(2N\log_2 N\) words 程度増えます。

実装例 (1056 ms) です。コード中の lid[i][j] に、「ノード \(i\) での二分探索の結果が \(j\) であるときの、左の子ノード \(2i\) に降りた先での二分探索の結果」を格納しています（rid も同様です）。筆者の実装では、Fractional Cascading を行わない実装 (640 ms) よりも遅くなってしまいました。

ところで、このデータ構造は、（疎な）\(2\) 次元セグメント木の \(2\) 次元目（各ノードに持たせるデータ構造）をセグメント木ではなく累積和にしたものとみなすこともできます（逆にいえば、このデータ構造で各ノードにセグメント木を持たせると、（疎な）\(2\) 次元セグメント木が作れるということです）。\(2\) 次元目にセグメント木以外のデータ構造を持たせる場面は他にも、たとえば点が変化しないときに矩形領域の min を求めたい場面で Sparse Table などを用いる例があります。累積和や Sparse Table のようにノードに持たせるデータ構造のクエリが \(o(\log N)\) 時間の場合、Fractional Cascading を用いることでクエリ時間計算量のオーダーの改善になります。