Merge Sort Tree

Merge Sort Tree 구현

query(): 자기보다 앞에 있는 것들 중 자신보다 큰 숫자의 개수

#include <vector>
using namespace std;

#define MAXN 500000
#define TREE_SIZE (MAXN * 4)

int nums[MAXN];

struct MergeSortTree {
private:
	vector<int> tree[TREE_SIZE];
    int n;	// input 개수
    
    void _build(int start, int end, int idx) {
    	if(start == end) {
        	tree[idx].push_back(nums[start]);
            return;
        }
        
        int mid = (start + end) >> 1;
        _build(start, mid, idx<<1);
        _build(mid+1, end, idx<<1|1);
        
        vector<int> &left = tree[idx<<1];
        vector<int> &right = tree[idx<<1|1];
        vector<int> &curr = tree[idx];
        
        curr.resize(left.size() + right.size());
        
        int l = 0, r = 0;
        int i = 0;
        while(l < left.size() && r < right.size())
        	curr[i++] = (left[l] > right[r]) ? left[l++] : right[r++];
            
        while(l < left.size()) curr[i++] = left[l++];
        while(r < right.size()) curr[i++] = right[r++];
    }
    
    int_upperBound(vector<int> &curr, int target) {
    	int low = 0, high = curr.size() - 1;
        
        while(low <= high) {
        	int mid = (low + high) >> 1;
            
            if(target < curr[mid]) low = mid + 1;
            else				   high = mid - 1;
        }
        
        return low;
    }
    
    int _query(int start, int end, int idx, int left, int right, int target) {
    	if(right < start || end < left) return 0;
        
        if(left <= start && end <= right) return _upperBound(tree[idx], target);
        
        int mid = (start + end) >> 1;
        
        return _query(start, mid, idx<<1, left, right, target) +
        	   _query(mid+1, end, idx<<1|1, left, right, target);
    }
    
public:
	void build(int n) {
    	this->n = n;
        _build(0, n, 1);
    }
    
    int query(int right, int target) {
    	return _query(0, n, 1, 0, right, target);
    }
};