c++ - セグメント ツリーを使用して配列内の反転の数をカウントする方法

Question

この問題は、変更されたマージソートを使用して解決できることを知っており、同じようにコーディングしました。ここで、 Segment Treeを使用してこの問題を解決したいと考えています。基本的に、配列を右から左にトラバースする場合、「現在の値よりも大きい値の数」をカウントする必要があります。このことは、セグメント ツリーによってどのように達成できますか?

セグメント ツリー ノードに格納する必要があるのは、どのような種類の情報ですか?

可能であればコードを提供してください。

Answer 1

例を挙げて順を追って説明しましょう。

arr      :  4 3 7 1
position :  0 1 2 3

まず、配列を {value, index} のペアとして降順に並べ替えます。

arr      :  7 4 3 1
index    :  2 0 1 3
position :  0 1 2 3

要素ごとに左から右に反復arr[i]-

各要素のindexクエリを実行し (範囲のクエリを実行し[0, arr[i].index]て左側の大きい数を取得します)、クエリ結果を対応するindex出力配列に配置します。

各クエリの後、それをカバーする対応するセグメント ツリー ノードをインクリメントしますindex。

このようにして、これまでに挿入された値よりも大きい値のみがから0にカウントされるようにします。index - 1arr[i]

以下の C++ 実装はより理にかなっています。

class SegmentTree {

    vector<int> segmentNode;

public:
    void init(int n) {
        int N = /* 2 * pow(2, ceil(log((double) n / log(2.0)))) - 1 */ 4 * n;
        segmentNode.resize(N, 0);
    }

    void insert(int node, int left, int right, const int indx) {
        if(indx < left or indx > right) {
            return;
        }
        if(left == right and indx == left) {
            segmentNode[node]++;
            return;
        }
        int leftNode = node << 1;
        int rightNode = leftNode | 1;
        int mid = left + (right - left) / 2;

        insert(leftNode, left, mid, indx);
        insert(rightNode, mid + 1, right, indx);

        segmentNode[node] = segmentNode[leftNode] + segmentNode[rightNode];
    }

    int query(int node, int left, int right, const int L, const int R) {
        if(left > R or right < L) {
            return 0;
        }
        if(left >= L and right <= R) {
            return segmentNode[node];
        }

        int leftNode = node << 1;
        int rightNode = leftNode | 1;
        int mid = left + (right - left) / 2;

        return query(leftNode, left, mid, L, R) + query(rightNode, mid + 1, right, L, R);
    }

};

vector<int> countGreater(vector<int>& nums) {
    vector<int> result;
    if(nums.empty()) {
        return result;
    }
    int n = (int)nums.size();
    vector<pair<int, int> > data(n);
    for(int i = 0; i < n; ++i) {
        data[i] = pair<int, int>(nums[i], i);
    }
    sort(data.begin(), data.end(), greater<pair<int, int> >());
    result.resize(n);
    SegmentTree segmentTree;
    segmentTree.init(n);
    for(int i = 0; i < n; ++i) {
        result[data[i].second] = segmentTree.query(1, 0, n - 1, 0, data[i].second);
        segmentTree.insert(1, 0, n - 1, data[i].second);
    }
    return result;
}

// Input : 4 3 7 1
// output: 0 1 0 3

これは簡単なものですが、他の典型的なセグメント ツリーの問題のように「明白」ではありません。ペンと紙で任意の入力をシミュレートすると役立ちます。

O(nlogn)BST、フェンウィック ツリー、およびマージ ソートを使用した他のアプローチがあります。