구간트리 (최대, 최소)

구간별 특정값들을 빠르게 계산하는 문제에서 필요함.

구간의 최대값, 커서가 움직이는 상태에서 가까운 위치 구하기 (cd홀더, 앱관리, 공사차량 등)

 

구간트리 생성, 업데이트, 쿼리 하는 코드

#include <stdio.h>
 
const int N = 50;
int tree[N * 4], A[N];
inline int Max(int a, int b) { return a > b ? a : b; }
 
void build(int now, int s, int e)
{
    if (s == e)    {
        tree[now] = s;    // 배열값을 넣어야 한다면 A[s] 같은 식으로 처리
        return;
    }
 
    int lch = now * 2;
    int rch = lch + 1;
    int m = (s + e) / 2;
 
    build(lch, s, m);
    build(rch, m + 1, e);
 
    tree[now] =  Max(tree[lch], tree[rch]);
}
 
void update(int now, int s, int e, int tg, int val)
{
    if (s == e)    {
        tree[now] = val;
        return;
    }
 
    int lch = now * 2;
    int rch = lch + 1;
    int m = (s + e) / 2;
 
    if (tg <= m)    update(lch, s, m, tg, val);
    else update(rch, m + 1, e, tg, val);
 
    tree[now] = Max(tree[lch], tree[rch]);
}
 
int query(int now, int s, int e, int qs, int qe)
{
    // 찾고자하는 범위가 트리의 범위에 없으면 리턴 0
    if (e < qs || qe < s)    return 0;
    // 찾고자하는 범위 안에 트리의 범위가 있으면 전체 리턴
    if (qs <= s && e <= qe)    return tree[now];
 
    int lch = now * 2;
    int rch = lch + 1;
    int m = (s + e) / 2;
 
    int lv = query(lch, s, m, qs, qe);
    int rv = query(rch, m + 1, e, qs, qe);
 
    return Max(lv, rv);
}
 
int main() {
    build(1, 1, N);
    //update(1, 1, N, 2, 7);
    int v = query(1, 1, N, 2, 3);
 
    printf("%d\n", v);
 
    return 0;
}