키네틱 세그먼트 트리 – 학습

1강 키네틱 세그먼트 트리: 움직이는 최값 공식

시간에 따라 변하는 일차함수

각 원소가 일차함수 $f_i(t) = a_i\ t + b_i$ 이고, 전역 시간 $$t$$ 가 단조 증가 한다고 하자. 처리할 연산:

시간을 $t \to t'$ ( $t' \ge t$ )로 전진.
구간 $$[l, r]$$ 의 현재 최솟값(또는 최댓값) 질의.
원소의 계수 갱신.

평범한 세그먼트 트리는 한 시점의 최값만 잡는다. 시간이 흐르면 "어느 함수가 최소인지"가 교차점 에서 바뀐다. 이를 amortize하는 것이 키네틱 세그먼트 트리(Kinetic Segment Tree, KST) 다.

certificate(증명서)와 melt time

각 내부 노드는 "내 서브트리의 최솟값은 자식 $$c$$ 가 들고 있다"는 사실을 저장한다. 이 사실이 깨지는 시점을 melt time 이라 부른다: 현재 최소인 함수와 다른 함수가 교차해 추월하는 시각.

노드의 melt time은 "현재 챔피언과 도전자 직선의 교점 시각" 중 가장 이른 것.

$t_{\text{melt}} = \min t' > t \ :\ f_{\text{loser}}(t') = f_{\text{winner}}(t').$

시간 전진: heaten

시간을 $$t'$$ 로 올릴 때, $t_{\text{melt}} \le t'$ 인 노드만 갱신하면 된다. 트리 전역의 melt time 최솟값을 (예: 별도 우선순위로) 추적하고, $$t'$$ 에 도달할 때까지 "녹은" 노드만 자식 정보로 다시 pull한다.

heaten(t'):
    while 트리 최소 melt time <= t':
        해당 노드 재계산(자식 비교 → 새 winner, 새 melt time)
        부모로 전파
    현재 시간 = t'

복잡도: amortized $O(\log^2 n)$ per advance

핵심은 녹는 횟수의 총합 분석이다. 두 직선은 최대 한 번 교차하므로, "한 노드에서 특정 함수쌍의 추월"은 시간 진행 동안 제한적으로 일어난다. Davenport–Schinzel 수열 이론으로, 일차함수 $$n$$ 개의 하부 포락선(lower envelope)의 복잡도는 $$O(n)$$ 이고, 세그먼트 트리 계층 전체에서 총 melt 횟수가 $O(n \log n \cdot \alpha(n))$ 수준으로 묶인다.

따라서 시간 전진 전체에 걸친 총비용이 $O((n + q)\log^2 n \cdot \alpha)$ 정도. 단조 시간이라는 가정이 결정적이다(역방향 시간은 깨짐).

가능한 질의 확장

질의	인코딩
구간 최솟값 $\min_i f_i(t)$	표준 KST
어떤 $$i$$ 가 최소인가	winner 인덱스 저장
합/카운트	melt마다 갱신, 단 amortize 주의

직선들의 동적 하부 포락선을 "단조 시간"으로 본다는 것이 핵심 관점이다. 다음 강의에서 구현.

2강 키네틱 세그먼트 트리 구현 공식

노드 구조

struct Line { long long a, b; };          // f(t) = a*t + b
long long curT;                           // 현재 전역 시간(단조 증가)

struct KST {
    int n;
    vector<Line> line;                    // 리프 함수
    vector<long long> val;                // 노드의 현재 최솟값
    vector<long long> melt;               // 노드의 melt time (없으면 INF)
};

두 직선의 교차 시각

$a_1 t + b_1 = a_2 t + b_2 \Rightarrow t = \dfrac{b_2 - b_1}{a_1 - a_2}$ . 현재보다 미래 의 교차만 의미 있다.

const long long INF = (1LL << 62);

// "winner가 미래에 loser에게 추월당하는 시각" (없으면 INF)
long long crossTime(Line winner, Line loser) {
    if (winner.a <= loser.a) return INF;      // loser가 더 가파르지 않으면 안 추월
    // winner가 지금 더 작지만 기울기가 더 큼 → 언젠가 추월당함
    long long num = loser.b - winner.b;        // > 0
    long long den = winner.a - loser.a;        // > 0
    long long t = num / den;                   // floor; 안전하게 +1 보정
    while (winner.a * t + winner.b <= loser.a * t + loser.b) t++;
    return t;
}

정수 시간 가정. 실수 시간이면 부동소수 오차를 조심한다.

pull: 자식에서 노드 재계산

void pull(int x, int lc, int rc) {
    Line wl = bestLine[lc], wr = bestLine[rc];
    if (wl.a*curT + wl.b <= wr.a*curT + wr.b) {
        bestLine[x] = wl; val[x] = wl.a*curT + wl.b;
        melt[x] = min(min(meltSub[lc], meltSub[rc]), crossTime(wl, wr));
    } else {
        bestLine[x] = wr; val[x] = wr.a*curT + wr.b;
        melt[x] = min(min(meltSub[lc], meltSub[rc]), crossTime(wr, wl));
    }
    meltSub[x] = melt[x];
}

bestLine[x]는 현재 시각에 $$x$$ 서브트리에서 최소인 직선. meltSub[x]는 서브트리 전체에서 가장 이른 melt time.

heaten: 시간 전진

void heaten(int x, int lo, int hi, long long t) {
    if (meltSub[x] > t) return;               // 안 녹음 → 건너뜀
    if (lo == hi) { meltSub[x] = INF; return; } // 리프는 함수 하나뿐
    int mid = (lo+hi)>>1, lc = x<<1, rc = lc|1;
    heaten(lc, lo, mid, t);
    heaten(rc, mid+1, hi, t);
    pull(x, lc, rc);
}

void advance(long long t) {                   // t >= curT
    curT = t;
    heaten(1, 0, n-1, t);
}

meltSub[x] > t인 가지는 통째로 가지치기 → amortized 비용 절감.

구간 최솟값 질의

long long queryMin(int x, int lo, int hi, int l, int r) {
    if (r < lo || hi < l) return INF;
    if (l <= lo && hi <= r) return val[x];
    int mid = (lo+hi)>>1, lc = x<<1, rc = lc|1;
    return min(queryMin(lc, lo, mid, l, r),
               queryMin(rc, mid+1, hi, l, r));
}

val[x]는 항상 curT 기준으로 최신(advance가 유지). 구간이 노드에 정렬돼 있으면 $O(\log n)$ .

갱신과 함정

직선 계수를 바꾸면 리프부터 pull로 위까지 갱신.
시간은 반드시 단조 증가 — 역방향 advance는 정의되지 않음(전체 재구축 필요).
crossTime의 floor/보정으로 off-by-one 방지. 오버플로는 __int128 또는 범위 점검.
최댓값 버전은 부등호와 crossTime 방향만 뒤집는다.

활용

시간에 따라 선형으로 변하는 비용/거리의 구간 최솟값.
동적 컨벡스헐 트릭(Li Chao와 달리 구간 + 단조 질의 시각).
DP에서 "시간 파라미터가 단조 증가"하는 최적화.

전체 비용은 amortized $O((n+q)\log^2 n)$ 수준. 단조 시간 가정이 성능의 핵심이다.