[그래프]Index Tree

Index Tree

포화 이진 트리 모양의 자료구조로 구간의 특징이 되는 값(합, 곱, 최대, 최소, gcd 등)을 처리할 때 이용

시간복잡도

point update : O(logN)
range query : O(logN)

구간합, 구간곱 예시 코드

#define ll long long

int n;    //수열의 수 및 노드의 수
vector<ll> tree;
int offset;

void construct(){
    for(offset = 1; offset < n; offset <<= 1);
    tree.resize(offset + offset--, 0);
}

ll sum(int s, int e){
    s += offset;    e += offset;
    ll ret = 0;
    while(s <= e){
        if(s % 2 == 1)    ret += tree[s++];
        if(e % 2 == 0)    ret += tree[e--];
        s >>= 2;
        e >>= 2;
    }
    return ret;
}

void sumUpdate(int idx, ll val){
    idx += offset;
    tree[idx] = val;
    while((idx >>= 1) > 0){
        tree[idx] = tree[idx << 1] + tree[(idx << 1) + 1];
    }
}

ll mul(int s, int e){
    s += offset;    e += offset;
    ll ret = 0;
    while(s <= e){
        if(s % 2 == 1)    ret *= tree[s++];
        if(e % 2 == 0)    ret *= tree[e--];
        s >>= 1;
        e >>= 1;
    }
    return ret;
}

void mulUpdate(int idx, ll val){
    idx += offset;
    tree[idx] = val;
    while((idx >>= 1) > 0){
        tree[idx] = tree[idx << 1] * tree[(idx << 1) + 1];
    }
}

구간 최대, 최소 예시 코드

#define INT_MAX 0x7fffffff
#define ll long long

int n;    //수열의 수 및 노드의 수
vector<ll> maxTree;
vector<ll> minTree;
int offset;

void construct(){
    for(offset = 1; offset < n; offset <<= 1);
    maxTree.resize(offset + offset, 0);
    minTree.resize(offset + offset--, INT_MAX);
}

void minUpdate(int idx, int val){
    idx += offset;
    minTree[idx] = val;
    while((idx >>= 1) > 0){
        minTree[idx] = min(minTree[idx << 1], minTree[(idx << 1) + 1];
    }
}

int getMin(int s, int e){
    s += offset;
    e += offset;

    int ret = INT_MAX;
    while(s <= e){
        ret = min(ret, min(minTree[s++], minTree[e--]));
        s >>= 1;
        e >>= 1;
    }
    return ret;
}

void maxUpdate(int idx, int val){
    idx += offset;
    maxTree[idx] = val;
    while((idx >>= 1) > 0){
        maxTree[idx] = max(maxTree[idx << 1], maxTree[(idx << 1) + 1];
    }
}

int getMax(int s, int e){
    s += offset;
    e += offset;

    int ret = 0;
    while(s <= e){
        ret = max(ret, max(maxTree[s++], maxTree[e--]));
        s >>= 1;
        e >>= 1;
    }
    return ret;
}

구간 최대공약수 예시 코드

#define ll long long

int n;
vector<int> tree;
int offset;

int seq[10] = {4, 2, 3, 5, 6, 5, 8, 8, 10, 12};
int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
}

void construct(){
    for(offset = 1; offset < n; offset <<= 1);
    tree.resize(offset + offset--, 0);
    
    for(int i = 1; i <= n; i++)    tree[i + offset] = seq[i - 1];
    for(int i = offset; i > 0; i--)    tree[i] = gcd(tree[i << 1], tree[(i << 1) + 1];
}

int query(int s, int e){
    s += offset;    e += offset;
    int ret = tree[s];
    
    while(s <= e){
        if(s % 2 == 1)    ret = gcd(ret, tree[s++]);
        if(e % 2 == 0)    ret = gcd(ret, tree[e--]);
        s >>= 1;
        e >>= 1;
    }
    return ret;
}

응용

• LIS(Least Incresing Subsequence)
• LCA(Least Common A Subsequence)