目次- ブルートフォース法 (1)

• ブルートフォース法 (2)
• 重量値セグメント木
• 演習問題

はじめに主席木を学習中に、重量値セグメント木の学習ノートを更新しておくのを思い出しました

まず、以下の問題を考えてみましょう：

配列に対して以下の操作を行います：

操作 (1)：配列中の第k小さい要素を問い合せます（答えは存在すると仮定）。 操作 (2)：ある要素を変更します。

最初はブルートフォース 방식으로考えてみましょう：

ブルートフォース法 (1)

操作 (1) に対しては、コピーを作成してソートし、第k番目の要素が答えになります。 操作 (2) に対しては、直接変更を行います。 時間計算量が大きすぎるため却下されます。

ブルートフォース法 (2)

バケット配列 b を用意し、b_i は値 i を持つ要素の個数を表します。 操作 (1) に対しては、1 から順に b_i を加算していき、累計が k を超えた時の i が答えになります。 ただし、値域が大きい可能性があるので、元の配列を離散化する必要があります。

小さな最適化：バケット配列に対して累積和を計算し、二分探索で答えを求められるようにします。 しかし、この方法には問題があります。変更操作の後で全体の累積和配列を更新する必要があるためです。

重量値セグメント木

本題に入りましょう。 ブルートフォース法 (2) に対して、累積和を使わずに高速に検索できるデータ構造はないでしょうか？ 例えば、O(log) の計算量でできるものは？

そう、セグメント木を使えます。先ほどのバケットをセグメント木に置き換えたものが重量値セグメント木です。一般的なセグメント木との違いは、重量値セグメント木は値をインデックスとして使う 点にあります。

次に、このセグメント木をどう維持するか説明します。各ノードは区間 [l,r] だけでなく、その範囲内の値の個数も保持します。 検索 위해서는、パラメータとして現在のノードの左側の区間 [1,l-1] にいくつの数字があるかを記録し、二分探索を行います。 左側の数字の個数が k 以上であれば左の子を再帰的に調べ、そうでなければ右の子を調べます。葉ノードに到達したら答えが得られます。 変更操作は更容易です。元の配列を記録しておき、まず値 a_i をセグメント木から1減らし、変更後の値を1増やしてから、a_i を更新するだけです。

これは臨時で作成した問題なので、コードはありません。

演習問題

これをテーマに！

BEFORE排序啊、用重量値セグメント木试试嘛~ 喂(#O)，别走啊~

上面的話请不要在意

では、この問題を考えてみましょう。重量値セグメント木を使って、各数字に対して、それより大きい前の数字の個数を数えることができます。

具体的にはどうやる？对于入力的每个数，先查询重量値セグメント木中比它大的数，也就是递归时记录右侧，即值>r的范围。然后，如果mid比当前查询的数大，那么自然是要走左儿子的。右儿子呢？仔细考虑就能發現，无论如何右儿子都要走。查询完后，把这个数加入重量値セグメント木就行了。

しかし、疑問に思う人がいるかもしれません：値が大きすぎます。怎么办？ 二つの解決策があります。

1. 離散化（説明を省略）
2. 動的ノード作成。接下来重点介绍。

動的ノード作成とは、必要な時にだけノードを作成し、不要な時は作成しないということです。 したがって、この場合はヒープストレージ方式は使えず、左右の子が誰かを記録する必要があります。 数が n 個しかなく、値域が大きいので、余分なノードを使用したくないです。 木を作成する際は、まず根ノードだけを作成し、必要に応じて他のノードを作成します：

struct SegTree {
    static const int MAXVAL = 1000000000;
    struct Node {
        int left, right;
        int l, r;
        int sum;
        Node() : left(0), right(0), sum(0) {}
    };
    vector<Node> tree;
    int nodeCount;
    
    SegTree() {
        tree.resize(1);
        tree[0] = Node();
        nodeCount = 0;
    }
    
    int createNode(int ll, int rr) {
        Node nd;
        nd.l = ll;
        nd.r = rr;
        tree.push_back(nd);
        return ++nodeCount;
    }
    
    void init() {
        nodeCount = 0;
        tree.clear();
        tree.resize(1);
        createNode(0, MAXVAL);
    }
    
    void update(int idx, int value, int delta) {
        if (tree[idx].l == tree[idx].r) {
            tree[idx].sum += delta;
            return;
        }
        int mid = (tree[idx].l + tree[idx].r) >> 1;
        if (value <= mid) {
            if (tree[idx].left == 0) {
                tree[idx].left = createNode(tree[idx].l, mid);
            }
            update(tree[idx].left, value, delta);
        } else {
            if (tree[idx].right == 0) {
                tree[idx].right = createNode(mid + 1, tree[idx].r);
            }
            update(tree[idx].right, value, delta);
        }
        tree[idx].sum = 0;
        if (tree[idx].left != 0) tree[idx].sum += tree[tree[idx].left].sum;
        if (tree[idx].right != 0) tree[idx].sum += tree[tree[idx].right].sum;
    }
    
    int query(int idx, int threshold) {
        if (idx == 0 || tree[idx].l >= threshold) {
            return tree[idx].sum;
        }
        int mid = (tree[idx].l + tree[idx].r) >> 1;
        int result = 0;
        if (threshold <= mid && tree[idx].left != 0) {
            result += query(tree[idx].left, threshold);
        }
        if (tree[idx].right != 0) {
            result += query(tree[idx].right, threshold);
        }
        return result;
    }
};

单点更新です。値を追加する際に、ノードが存在しない場合があります。その場合は新規作成します。

最後はクエリです。代码は以下のようになります：

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    SegTree st;
    st.init();
    
    long long answer = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        answer += st.query(1, x + 1);
        st.update(1, x, 1);
    }
    
    cout << answer << '\n';
    return 0;
}

これで問題は解決しました！