사탕상자

21 Sep 2017

segment tree
kth

Problem

Idea

leaf의 개수가 100만 이기에 메모리는 가능할 것같다.
만약 leaf개수가 천만이라면:
4000만 * 4byte (int) = 150mb 가 넘을 수 있기에 주의

query 구현은 kth 번째 수 찾기와 같다

int kth(node, s, e, kth) {
    if (s == e) {
        return s;
    }
    mid = (s + e) >> 1;

    if (tree[node * 2] >= kth) {
        return find(node * 2, s, mid, kth);        
    } else {
        return find(node * 2+1, mid+1, e, kth - tree[node * 2]);
    }
}

int query(kth) {
    return kth(1, 0, MAX, kth);
}

static int query(int val) {
    int s = 1;
    int e = MAX;
    int node = 1;

    int mid = (s + e) / 2;
    int left = 0;
    while (s != e) {
        left = tree[node * 2];
        mid = (s + e) / 2;
        if (left >= val) {
            node = node * 2;
            e = mid;
        } else {
            node = node * 2 + 1;
            val = val - left;
            s = mid + 1;
        }
    }
    return s;
}