[Java] Index Tree / Segment Tree Lazy Propagation

https://www.acmicpc.net/blog/view/26

세그먼트 트리 나중에 업데이트 해야지!

https://steady-coding.tistory.com/129

[BOJ] 백준 6549번 : 히스토그램에서 가장 큰 직사각형 (JAVA)

index tree는 기존의 세그트리와 다르게

최소(최대)값이 저장되어있지 않고, 최소(최대)값의 "위치"를 담고 있다.

여기서의 위치는 1~n번 값을 따로 저장해놓은 배열에서의 위치를 의미.

 

segment tree lazt propagation은

10999 구간합2 처럼 "값 업데이트가 여러 범위에 걸쳐 일어날 경우" 매번 해당 칸들을 전부 업데이트해주면

tle가 나오기 때문에, left <= lo && hi <= right 일때 그 밑의 노드들의 업데이트는 미루고

lazy 배열에 저장해두었다가 나중에 탐색할 일이 있을 때 방문하는 김에 lazy()로 갱신!

(lazy[i] != 0이면 lazy로 갱신할 값이 존재한다는 뜻)

 

파란 노드를 루트로 가지는 모든 노드들을 업데이트하지 않고,

파란 노드에서 좌우의 노드에게 lazy값을 추가해준 뒤 업데이트를 멈춘다!

 

static long init(int left, int right, int node){    
    if (left == right) return tree[node] = val[left];

    int mid = (left + right) / 2;
    return tree[node] = init(left, mid, node * 2) + init(mid + 1, right, node * 2 + 1);
}

제일 처음에 들어오는 값들은 init으로 정상적으로 받아준다

 

static void update(int lo, int hi, int node, int left, int right, long value){
    lazy(lo, hi, node);

    if (hi < left || right < lo) return;
    if (left <= lo && hi <= right){
        tree[node] += (hi - lo + 1) * value;
        if (lo != hi){
            lazy[node * 2] += value;
            lazy[node * 2 + 1] += value;
        }
        return;
    }

    int mid = (lo + hi) / 2;
    update(lo, mid, node * 2, left, right, value);
    update(mid + 1, hi, node * 2 + 1, left, right, value);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

static void lazy(int lo, int hi, int node){
    if (lazy[node] != 0){
        tree[node] += lazy[node] * (hi - lo + 1);
        if (lo != hi){
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
}

업데이트가 일어나면 매 노드 방문시마다 항상 lazy에 값이 밀려있는지 확인

해당 노드가 루트인 경우 모두 갱신해야한다면

"올바르게" tree[node] 값 갱신 => value 값을 (hi - lo + 1)번 더해줘야함.

 

static long sum(int lo, int hi, int node, int left, int right){
    lazy(lo, hi, node);

    if (hi < left || right < lo) return 0;
    if (left <= lo && hi <= right) return tree[node];

    int mid = (lo + hi) / 2;
    return sum(lo, mid, node * 2, left, right) + sum(mid + 1, hi, node * 2 + 1, left, right);
}

합을 구해줄때도 꼭 각 노드 방문시마다 lazy 체크