静的sorted range index・Merge Sort Tree
各canonical区間へsorted列とprefix aggregateを構築し、値域境界付きのrange count/sumを二分探索で答える。
この典型を扱う単元: 静的sorted range index・Merge Sort Tree
検索別名: Merge Sort Tree、merge sort tree、静的range tree
未知問からこの典型を見つける手掛かり
- 扱う対象
- prefix sum
- sorted node array
- 静的配列
- 使う手掛かり
- range count
- range sum
- 区間内で値以下
- 保つ不変量
- canonical cover
- node内sort順
- 求めるもの
- 値域付き区間query
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 更新可能な最小十分要約
関連する典型
- Segment Treeのcanonical区間分解: query区間をcanonical node列へ分け、各nodeのsorted列を二分探索する実装に使う。
学習成果と学習単位
各canonical区間へsorted列とprefix aggregateを構築し、値域境界付きのrange count/sumを二分探索で答える。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
静的sorted range index・Merge Sort Treeで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。