バイナリインデックストリー

単点更新、範囲照会が可能なデータ構造です。

典型的な問題として、数列の特定の位置を更新し、任意の区間の合計を求める操作が考えられます。

このデータ構造の核となるのがlowbit関数です。これは整数xに対して、xの最も右側にある1を含む部分を返す操作です。具体的にはx&-xと表現できます。

実装の基本となるのはtree配列です。各要素tree[i]は、特定の区間の要素の合計を保持しています。この定義はlowbitに依存しています。

最も重要な2つの関数を見てみましょう：

// 両方の関数の時間計算量はO(log n)です
// x&-xの部分がlowbit操作に相当します
void update(int index, int delta) {
    while(index <= n) {
        tree[index] += delta;
        index += index & -index;
    }
}

// query(index)は1からindexまでの区間の合計を返します
int query(int index) {
    int sum = 0;
    while(index > 0) {
        sum += tree[index];
        index -= index & -index;
    }
    return sum;
}

// lからrの区間の合計を求めるにはquery(r) - query(l-1)を使用します

これで基本的な実装は完了です。

非常にシンプルですが、バイナリインデックストリーの応用範囲は広いです。

ここに一つの練習問題を紹介します。

この問題は興味深いものです。セグメントツリーでも解けますが、より効率的な解法がバイナリインデックストリーを使用することです。特に、この問題では差分数列を維持している点が特徴的です。つまり、query(x)を実行すると、x番目の要素の実際の値が得られるのです！これは非常に強力な機能です。バイナリインデックストリーはコードが短く、定数も小さいのに対し、セグメントツリーは実装が複雑でデバッグも大変、コードも長く、定数も大きいという欠点があります。

それでは、この問題のコード例を示します：

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const int MAX = 200005;
ll n, m;
vector<ll> tree(MAX);

void update(int index, ll delta) {
    while(index <= n) {
        tree[index] += delta;
        index += index & -index;
    }
}

ll query(int index) {
    ll sum = 0;
    while(index > 0) {
        sum += tree[index];
        index -= index & -index;
    }
    return sum;
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        update(i, x);
        update(i + 1, -x);
    }
    
    while(m--) {
        ll op;
        cin >> op;
        op++;
        ll x = query(op);
        update(op, -x);
        update(op + 1, x);
        update(1, x / n);
        update(n + 1, -x / n);
        update(op + 1, 1);
        update(min(n, op + x % n) + 1, -1);
        if(op + x % n > n) {
            update(1, 1);
            update(op + x % n - n + 1, -1);
        }
    }
    
    for(int i = 1; i <= n; i++) {
        cout << query(i) << " ";
    }
    return 0;
}

ご覧の通り、この実装はたった18行です。一方、セグメントツリーで同じ問題を解く場合、どれだけ圧縮しても少なくとも50行以上必要になります。バイナリインデックストリーはどれほど便利かお分かりでしょう。したがって、セグメントツリーは良いツールではなく、使わないようにしましょう

セグメントツリー

セグメントツリーはコード量が多く、定数も大きく、実装やデバッグも難しいアルゴリズムですが、その応用範囲は広いです！範囲更新と範囲照会を両方サポートできます。時間計算量はO(n log n)で、許容範囲内です。

では、典型的な問題を見てみましょう！

明らかに範囲更新と範囲照求が必要な問題です。

セグメントツリーの本質はLazyTag（遅延伝播）にあります。

残念ながら、これは問題解説ではなく学習ノートなので、詳細は割愛します。

コード例を示します！（少し見にくいかもしれません）

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const int MAX = 100005;
int n, m;
vector<ll> arr(MAX), seg(MAX * 4), lazy(MAX * 4);

ll read() {
    ll num = 0, sign = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') sign = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        num = num * 10 + ch - '0';
        ch = getchar();
    }
    return num * sign;
}

void write(ll x) {
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int left_child(int x) { return (x << 1); }
int right_child(int x) { return (x << 1 | 1); }

void push_up(int x) {
    seg[x] = seg[left_child(x)] + seg[right_child(x)];
}

void build(int x, int l, int r) {
    if(l == r) {
        seg[x] = arr[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(left_child(x), l, mid);
    build(right_child(x), mid + 1, r);
    push_up(x);
    lazy[x] = 0;
}

void add(int x, int l, int r, ll k) {
    seg[x] += (r - l + 1) * k;
    lazy[x] += k;
}

void push_down(int x, int l, int r) {
    if(!lazy[x]) return;
    int mid = (l + r) >> 1;
    add(left_child(x), l, mid, lazy[x]);
    add(right_child(x), mid + 1, r, lazy[x]);
    lazy[x] = 0;
}

void update(int x, int l, int r, int L, int R, ll k) {
    if(r < L || R < l) return;
    if(L <= l && r <= R) {
        add(x, l, r, k);
        return;
    }
    push_down(x, l, r);
    int mid = (l + r) >> 1;
    update(left_child(x), l, mid, L, R, k);
    update(right_child(x), mid + 1, r, L, R, k);
    push_up(x);
}

ll query(int x, int l, int r, int L, int R) {
    if(r < L || R < l) return 0;
    if(L <= l && r <= R) return seg[x];
    push_down(x, l, r);
    int mid = (l + r) >> 1;
    return query(left_child(x), l, mid, L, R) + query(right_child(x), mid + 1, r, L, R);
}

int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; i++) arr[i] = read();
    build(1, 1, n);
    
    while(m--) {
        int op = read();
        if(op == 1) {
            int l = read(), r = read();
            ll k = read();
            update(1, 1, n, l, r, k);
        } else {
            int l = read(), r = read();
            write(query(1, 1, n, l, r));
            cout << "\n";
        }
    }
    return 0;
}

かなり圧縮されていますが、それでも47行あります！

これがセグメントツリーの基本的な実装です。

セグメントツリーの別の典型的な問題として、乗算と加算の両方をサポートする問題があります。この場合、LazyTagの実装はより複雑になります。

コードは省略します。怠け者は怠け者のままでしょう

次に、もう一つの練習問題を紹介します！ちょっと探してきます

見つかりました！

この問題は面白いものです。デバックにかなり時間がかかりました

主なポイントは、セグメントツリーが4つの値を維持する必要があることです：最大値、最大値の個数、次に大きい値、次に大きい値の個数。そして、これらを結合するpush_up関数は比較的複雑な実装が必要です。一つずつ比較する方法もありますが、効率が悪いため、私はmapとpriority_queueを使用しました。私はSTLの達人で、結合処理に2つのSTLを使うくらいのこと。全体として、細かい部分が多く、デバックが非常に難しいです。

コード例を示します。コーディングスタイルは少し変わっており、デバックの過程で少し乱雑になっていますが、ご容赦ください。

#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;

const int MAX = 200005;
int n, Q;
vector<ll> arr(MAX);

struct Node {
    int max1, max2;
    int cnt1, cnt2;
} seg[MAX * 4];

ll read() {
    ll num = 0, sign = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') sign = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        num = num * 10 + ch - '0';
        ch = getchar();
    }
    return num * sign;
}

int left_child(int x) { return (x << 1); }
int right_child(int x) { return (x << 1 | 1); }

void push_up(int x) {
    map<int, int> freq_map;
    priority_queue<int> pq;
    
    pq.push(seg[left_child(x)].max1);
    pq.push(seg[left_child(x)].max2);
    pq.push(seg[right_child(x)].max1);
    pq.push(seg[right_child(x)].max2);
    
    freq_map[seg[left_child(x)].max1] += seg[left_child(x)].cnt1;
    freq_map[seg[left_child(x)].max2] += seg[left_child(x)].cnt2;
    freq_map[seg[right_child(x)].max1] += seg[right_child(x)].cnt1;
    freq_map[seg[right_child(x)].max2] += seg[right_child(x)].cnt2;
    
    if(freq_map.size() == 1) {
        seg[x].max1 = pq.top();
        seg[x].max2 = pq.top();
        seg[x].cnt1 = freq_map[seg[x].max1];
        seg[x].cnt2 = seg[x].cnt1;
        return;
    }
    
    seg[x].max1 = pq.top();
    seg[x].cnt1 = freq_map[pq.top()];
    while(!pq.empty() && pq.top() == seg[x].max1) pq.pop();
    
    seg[x].max2 = pq.top();
    seg[x].cnt2 = freq_map[pq.top()];
}

void build(int x, int l, int r) {
    if(l == r) {
        seg[x] = {arr[l], 0, 1, 0};
        return;
    }
    int mid = (l + r) >> 1;
    build(left_child(x), l, mid);
    build(right_child(x), mid + 1, r);
    push_up(x);
}

void update(int x, int l, int r, int pos, ll k) {
    if(l == pos && r == pos) {
        seg[x] = {k, 0, 1, 0};
        return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) update(left_child(x), l, mid, pos, k);
    else update(right_child(x), mid + 1, r, pos, k);
    push_up(x);
}

Node merge_nodes(Node a, Node b) {
    map<int, int> freq_map;
    priority_queue<int> pq;
    Node result;
    
    pq.push(a.max1);
    pq.push(a.max2);
    pq.push(b.max1);
    pq.push(b.max2);
    
    freq_map[a.max1] += a.cnt1;
    freq_map[a.max2] += a.cnt2;
    freq_map[b.max1] += b.cnt1;
    freq_map[b.max2] += b.cnt2;
    
    if(freq_map.size() == 1) {
        result.max1 = pq.top();
        result.max2 = pq.top();
        result.cnt1 = freq_map[result.max1];
        result.cnt2 = result.cnt1;
        return result;
    }
    
    result.max1 = pq.top();
    result.cnt1 = freq_map[pq.top()];
    while(!pq.empty() && pq.top() == result.max1) pq.pop();
    
    result.max2 = pq.top();
    result.cnt2 = freq_map[pq.top()];
    return result;
}

Node query(int x, int l, int r, int L, int R) {
    if(L <= l && r <= R) return seg[x];
    int mid = (l + r) >> 1;
    if(R <= mid) return query(left_child(x), l, mid, L, R);
    if(L > mid) return query(right_child(x), mid + 1, r, L, R);
    return merge_nodes(query(left_child(x), l, mid, L, R), 
                      query(right_child(x), mid + 1, r, L, R));
}

int main() {
    n = read(), Q = read();
    for(int i = 1; i <= n; i++) arr[i] = read();
    build(1, 1, n);
    
    while(Q--) {
        int op = read();
        if(op == 1) {
            int pos = read();
            ll k = read();
            update(1, 1, n, pos, k);
        } else {
            int l = read(), r = read();
            Node result = query(1, 1, n, l, r);
            cout << (result.max2 == result.max1 ? 0 : result.cnt2) << "\n";
        }
    }
    return 0;
}

これでも70〜80行のコードになるでしょう。細かい部分が山積みです。したがって、セグメントツリーの使用はできるだけ避けたほうが良いかもしれません。しかし、その応用範囲の広さから、学ぶ必要があるのです！

まとめ

バイナリインデックストリーは良いツールですが、セグメントツリーはそうではありません。そして、それ以上のことはありません

このまとめは正しいので、なぜそれを削除するのでしょうか？

したがって、バイナリインデックストリーは基本的に自由に使用できます。細かい部分もなく、コード量も非常に少なく、非常に親しみやすいデータ構造です。一方、セグメントツリーは、試験場で遭遇した場合、すぐに実装を開始せず、最後の1時間程度を確保して攻略するようにしてください。一度で正しく実装できれば良いですが、小さなバグが発生すると、心が崩壊し、後の問題に取り組む気力が失われ、多くの時間を無駄にしてしまうかもしれません。

セグメントツリーを完全にマスターするための第一歩は、デバックの方法を学ぶことです！