接頭和と差分配列の応用
接頭和 & 差分配列
計算量最適化のための基本技術
接頭和は複数回の区間クエリを高速化する手法。配列arr[N]に対してpre_sum[N]を構築し、
pre_sum[i] = pre_sum[i-1] + arr[i]と定義する。インデックスは1から始める必要がある。
実践問題
N都市を結ぶ道路があり、各セグメントの移動コストが与えられる。伝送装置を使って最大kセグメント飛躍可能。ただし1回の ...
7月24日 18:21 投稿
奇想天外なアイデアがコードで現実になる場所
7月24日 18:21 投稿