プレフィックス和と差分アルゴリズムの理解とC++実装
プレフィックス和アルゴリズム
基本概念
プレフィックス和は配列処理技術の一種で、事前計算により部分区間の和をO(1)で取得可能にします。入力配列をdataとすると、プレフィックス配列prefは次のように定義されます：
pref[i] = data[0] + data[1] + ... + data[i]
pref[0] = data[0]
構築方法
C++による実装例：
vector<int> constructPrefixArray(const vector& ...
5月21日 10:20 投稿