kazuma8128’s blog

競プロの面白い問題を解きます

Fenwick Tree

区間内の x 未満の値の個数, 区間内の k 番目に小さい値

クエリの定義 基本的なテクニック 値の変更なし ver オフラインクエリ rank kth_min オンラインクエリ rank kth_min まとめ 値の変更あり ver X[p] の値を v に変更 rank kth_min その他 値の変更/挿入あり ver クエリの定義 長さ N の整数列 X に対して, 以…

k 番目に小さい値を取得可能な集合を管理するデータ構造

前提 配列(または bitset) Fenwick Tree 平方分割 Trie(動的 Segment Tree) 平衡二分木 おまけ 前提 集合に対して N 個の 追加・削除・k番目に小さい値の取得 のクエリがくるとします. 集合の要素は順序が付けられるものだけ考えます. 要素が非負整数の…

HackerRank Cube Summation

問題文 https://www.hackerrank.com/challenges/cube-summation/problem 問題概要 N x N x N の3次元配列がある. (N 一点更新クエリと, 範囲和クエリがくるので処理せよ. 解法 Nが小さいので 3 次元の Fenwick Tree を書けば終わりです.3次元は流石にライブ…