noshi91のメモ

データ構造のある風景

2019-10-05から1日間の記事一覧

区間代入/区間積 Θ(logN)/query

概要 遅延セグメント木は様々な区間操作が で可能です。 一方で、代入と積の組み合わせは累乗を計算する必要があり、そのままでは に悪化してしまいます。 本稿では空間計算量を に抑えたまま、 で処理する手法を提案します。 また、積に限らず一般のモノイ…