接頭和 & 差分配列

• 計算量最適化のための基本技術
• 接頭和は複数回の区間クエリを高速化する手法。配列arr[N]に対してpre_sum[N]を構築し、

pre_sum[i] = pre_sum[i-1] + arr[i]と定義する。インデックスは1から始める必要がある。

実践問題

N都市を結ぶ道路があり、各セグメントの移動コストが与えられる。伝送装置を使って最大kセグメント飛躍可能。ただし1回のみ使用可能。

ll solve() {
    ll n, k;
    cin >> n >> k;
    vector<ll> cost(n+1), pre_sum(n+1);
    for(ll i=1; i<=n; i++) {
        cin >> cost[i];
        pre_sum[i] = pre_sum[i-1] + cost[i];
    }
    
    if(k >= n) return 0;
    
    ll max_jump = 0;
    for(ll i=k; i<=n; i++) {
        max_jump = max(max_jump, pre_sum[i] - pre_sum[i-k]);
    }
    
    return pre_sum[n] - max_jump;
}

差分配列

• 接頭和の逆操作
• 区間更新をO(1)で処理可能

差分配列diff[N]を構築し、区間[l,r]にxを加算する操作は：

void range_add(int l, int r, int x) {
    diff[l] += x;
    diff[r+1] -= x;
}

応用例

鉄道区間の利用回数カウント問題。各区間で紙の切符かICカードのどちらがお得かを判定。

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> path(m+1), diff(n+2, 0);
    
    for(int i=1; i<=m; i++) cin >> path[i];
    
    for(int i=1; i> a >> b >> c;
        res += min(diff[i]*a, diff[i]*b + c);
    }
    
    cout << res << endl;
}

二次元接頭和 & 差分

二次元配列の累積和計算公式：

矩形領域の合計計算：

土地選定問題

void calc_prefix() {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + grid[i][j];
        }
    }
}

int main() {
    int n, m, c;
    cin >> n >> m >> c;
    
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin >> grid[i][j];
        }
    }
    
    calc_prefix();
    
    int max_val = -INF;
    for(int i=1; i<=n-c+1; i++) {
        for(int j=1; j<=m-c+1; j++) {
            int x1=i, y1=j, x2=i+c-1, y2=j+c-1;
            int val = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1];
            if(val > max_val) {
                max_val = val;
                ans_x = i, ans_y = j;
            }
        }
    }
    
    cout << ans_x << " " << ans_y << endl;
}