差分配列

差分配列は、区間更新や多次元の範囲操作に効率的に対処するために使用されます。

一維差分

一連の値を変更する際、差分配列を使用して効率よく計算できます。

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n;
    int a[n + 2], diff[n + 2];
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        diff[i] = a[i] - a[i - 1];
    }
    diff[n + 1] = -a[n];
    cin >> m;
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        diff[u] += w;
        diff[v + 1] -= w;
    }
    for (int i = 1; i <= n; ++i) {
        a[i] = a[i - 1] + diff[i];
        cout << a[i] << ' ';
    }
    return 0;
}

二維差分

二次元の範囲に対して同様の手法が適用可能です。

#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    int diff[1002][1002], grid[1002][1002];
    for (int i = 0; i < n; ++i) {
        int lx, ly, rx, ry;
        cin >> lx >> ly >> rx >> ry;
        diff[lx][ly]++;
        diff[rx][ly]--;
        diff[lx][ry]--;
        diff[rx][ry]++;
    }
    int count = 0;
    for (int x = 0; x <= 1001; ++x) {
        for (int y = 0; y <= 1001; ++y) {
            grid[x][y] = grid[x - 1][y] + grid[x][y - 1] - grid[x - 1][y - 1] + diff[x][y];
            if (grid[x][y] == k) count++;
        }
    }
    cout << count;
    return 0;
}

再帰関係

再帰的な数列の生成方法について説明します。

フィボナッチ数列

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long fib[4001];
    fib[0] = fib[1] = 1;
    for (int i = 2; i <= n; ++i) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    cout << fib[n];
    return 0;
}

セグメントツリー

範囲クエリや更新操作を効率的に行うために使われます。

#include <iostream>
using namespace std;

struct Node {
    int l, r, minVal, lazy;
};

Node tree[4 * 1000005];
int arr[1000005];

void build(int idx, int left, int right) {
    tree[idx].l = left;
    tree[idx].r = right;
    if (left == right) {
        tree[idx].minVal = arr[left];
        return;
    }
    int mid = (left + right) / 2;
    build(2 * idx, left, mid);
    build(2 * idx + 1, mid + 1, right);
    tree[idx].minVal = min(tree[2 * idx].minVal, tree[2 * idx + 1].minVal);
}

void pushDown(int idx) {
    if (tree[idx].lazy != 0) {
        tree[2 * idx].minVal -= tree[idx].lazy;
        tree[2 * idx + 1].minVal -= tree[idx].lazy;
        tree[2 * idx].lazy += tree[idx].lazy;
        tree[2 * idx + 1].lazy += tree[idx].lazy;
        tree[idx].lazy = 0;
    }
}

void update(int idx, int L, int R, int val) {
    if (tree[idx].l >= L && tree[idx].r <= R) {
        tree[idx].minVal -= val;
        tree[idx].lazy += val;
        return;
    }
    pushDown(idx);
    int mid = (tree[idx].l + tree[idx].r) / 2;
    if (L <= mid) update(2 * idx, L, R, val);
    if (R > mid) update(2 * idx + 1, L, R, val);
    tree[idx].minVal = min(tree[2 * idx].minVal, tree[2 * idx + 1].minVal);
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    build(1, 1, n);
    for (int i = 0; i < m; ++i) {
        int d, s, t;
        cin >> d >> s >> t;
        update(1, s, t, d);
        if (tree[1].minVal < 0) {
            cout << "-1 " << i + 1;
            return 0;
        }
    }
    cout << "0";
    return 0;
}

最短経路問題

BFSやダイクストラ法を使って最短経路を求めることができます。

例題: 最短経路計数

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MOD = 100003;
vector<int> graph[1000005];
int distanceArr[1000005], countArr[1000005];

void bfs(int start) {
    queue<int> q;
    q.push(start);
    distanceArr[start] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto &v : graph[u]) {
            if (distanceArr[v] > distanceArr[u] + 1) {
                distanceArr[v] = distanceArr[u] + 1;
                q.push(v);
            }
        }
    }
}

void calculate(int start) {
    queue<int> q;
    q.push(start);
    countArr[start] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto &v : graph[u]) {
            if (distanceArr[u] + 1 == distanceArr[v]) {
                countArr[v] = (countArr[v] + countArr[u]) % MOD;
                if (countArr[v] == 1) q.push(v);
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    fill(distanceArr, distanceArr + n + 1, 1e9);
    bfs(1);
    calculate(1);
    for (int i = 1; i <= n; ++i) {
        if (distanceArr[i] == 1e9) cout << "0\n";
        else cout << countArr[i] % MOD << '\n';
    }
    return 0;
}