MergeSortTree

 

1. 구간에서 특정 값보다 큰 값의 개수 구하기
2. 구간에서 특정 값보다 작은 값의 개수 구하기
3. 구간에서 특정 값의 개수 구하기
4. 구간에서 특정 범위에 속하는 값들의 개수 구하기
5. 구간에서 k번째 큰,작은 값 구하기
6. 구간 내 중복된 값 찾기
7. 구간에서 특정 값의 등장 여부 확인

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class MergeSortTree {
public:
    MergeSortTree(const vector<int>& arr) {
        n = arr.size();
        tree.resize(4 * n);
        build(arr, 1, 0, n - 1);
    }

    int query(int left, int right, int k) {
        return query_util(1, 0, n - 1, left, right, k);
    }
private:
    int n;
    vector< vector<int> > tree;

    void build(const vector<int>&arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = vector<int>(1, arr[start]);
        }
        else {
            int mid = (start + end) / 2;
            build(arr, node * 2, start, mid);
            build(arr, node * 2 + 1, mid + 1, end);
            merge(tree[node * 2].begin(), tree[node * 2].end(), \
            tree[node * 2 + 1].begin(), tree[node * 2 + 1].end(), \
            back_inserter(tree[node]));
        }
    }

    int query_util(int node, int start, int end, int left, int right, int k) {
        if (right < start || end < left) {
            return 0;
        }
        if (left <= start && end <= right) {
            return tree[node].end() - upper_bound(tree[node].begin(), tree[node].end(), k);
        }
        int mid = (start + end) / 2;
        int left_result = query_util(node * 2, start, mid, left, right, k);
        int right_result = query_util(node * 2 + 1, mid + 1, end, left, right, k);
        return left_result + right_result;
    }
};