接頭和と差分配列の応用
接頭和 & 差分配列
計算量最適化のための基本技術
接頭和は複数回の区間クエリを高速化する手法。配列arr[N]に対してpre_sum[N]を構築し、
pre_sum[i] = pre_sum[i-1] + arr[i]と定義する。インデックスは1から始める必要がある。
実践問題
N都市を結ぶ道路があり、各セグメントの移動コストが与えられる。伝送装置を使って最大kセグメント飛躍可能。ただし1回の ...
7月24日 18:21 投稿
アルゴリズムの応用とデータ構造
差分配列差分配列は、区間更新や多次元の範囲操作に効率的に対処するために使用されます。
一維差分
一連の値を変更する際、差分配列を使用して効率よく計算できます。
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n;
int a[n + 2], diff[n + 2];
for (int i = 1; i > a[i];
diff[i] = a[i] - a[i - 1];
...
7月22日 05:10 投稿
差分配列と累積和のアルゴリズム
差分配列と累積和
テンプレート（疑似コード）
// 元データの読み込み: n, m, a
n, m = 入力()
for i = 0 to n-1:
a[i] = 入力() // 元の配列
// 差分配列の構築
for i = 0 to n-1:
diff[i] = a[i] - a[i-1]
// 区間操作
while m > 0:
m = m - 1
l, r, value = 入力()
diff[l] = diff[l] + value
diff[r+1] = diff[r+1] - value
// 累積和で ...
5月18日 12:33 投稿