差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン
前のリビジョン
次のリビジョン両方とも次のリビジョン
programming_algorithm:data_structure:sparse_table [2019/12/05] ikatakosprogramming_algorithm:data_structure:sparse_table [2019/12/05] – [±1-RmQ] ikatakos
行 94: 行 94:
 $A=\{A_0,A_1,...,A_{N-1}\}$ の要素が、必ず「左の値から1増えるか1減るかのどちらか」で変化していく配列の最小値/最大値を求める場合。 $A=\{A_0,A_1,...,A_{N-1}\}$ の要素が、必ず「左の値から1増えるか1減るかのどちらか」で変化していく配列の最小値/最大値を求める場合。
  
-この場合、実装はちょっとややこしくなるが、事前計算量と空間を $O(N\log{N})$ から $O(N)$ に落とすことができる。+この場合、実装はちょっとややこしくなるが、クエリ応答は $O(1)$ のまま、事前計算量と空間を $O(N\log{N})$ から $O(N)$ に落とすことができる。
  
 なかなか特殊な条件に見えるが、木の最小共通祖先だったり、たまに使える。 なかなか特殊な条件に見えるが、木の最小共通祖先だったり、たまに使える。
行 108: 行 108:
   * ブロックを1要素として、SparseTableを構築する   * ブロックを1要素として、SparseTableを構築する
   * クエリに対して、完全に覆われるブロック内の最小値はSparseTableで求められる   * クエリに対して、完全に覆われるブロック内の最小値はSparseTableで求められる
-  * はみ出る部分は個別に計算するが、変化パターンが+1か-1のみなので、どのパターンが事前計算して持っておいても大したサイズにならない+  * はみ出る部分は個別に計算するが、変化パターンが限られるので、事前計算して持っておいても大したサイズにならない
  
       | 1  2  3 | 4  5  6 | 7  8  9 | 10 11 12 | 13 14 15 | 16 17 18 | 19 20 21 | 22 23 24 | 25 26 27 | 28 29 30 |       | 1  2  3 | 4  5  6 | 7  8  9 | 10 11 12 | 13 14 15 | 16 17 18 | 19 20 21 | 22 23 24 | 25 26 27 | 28 29 30 |
programming_algorithm/data_structure/sparse_table.txt · 最終更新: 2023/10/13 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0