리차오 트리 (Li Chao Tree)

2026년 6월 24일 · 수정 2026년 6월 24일 · 📖 약 5분 · 1,410자/단어 #algorithm #data-structure #li-chao-tree #convex-hull-trick #segment-tree

정의

리차오 트리 (Li Chao Tree) 는 평면 상의 직선 (또는 선분) 집합에서 특정 x좌표에서의 최댓값 (또는 최솟값) 을 O(log N) 에 구하는 자료구조. 세그먼트 트리 변형으로, 각 노드에 해당 구간에서 “가장 위(또는 아래)에 있는 직선” 하나를 저장하고, 나머지는 재귀적으로 좌우 자식에 분산.

직선 추가 O(log N), 점 쿼리 O(log N). CHT (Convex Hull Trick)의 일반화이며, 직선 순서 제약 없이 임의 순서 삽입 가능.

중국의 Li Chao가 2014년경 제안, PS에서는 DP 최적화 (Convex Hull Trick의 오프라인 대안) 및 기하 문제에 널리 쓰임.

문제 상황과 동기

N개의 직선 y = a_i * x + b_i 가 주어질 때, 쿼리 “x = q 에서의 최댓값”을 Q번 처리:

naive: 모든 직선 N개 평가, O(N) × Q = O(NQ).
CHT (Convex Hull Trick): 직선을 기울기 순으로 정렬하면 O(N + Q), 단 순서 고정.
Li Chao Tree: 임의 순서 삽입 가능, O(log N) 삽입 + O(log N) 쿼리.

핵심 통찰: 세그먼트 트리의 각 구간 [l, r] 에서 중앙값 mid 기준으로 “mid에서 최대인 직선”을 노드에 저장하고, 나머지는 좌우로 분할. 쿼리 시 루트부터 리프까지 O(log N) 경로의 직선만 확인.

시각화

핵심 아이디어

invariant: 각 노드 [l, r] 의 mid 지점에서 최대(또는 최소)인 직선 하나를 저장. 삽입 시 기존 직선과 새 직선을 mid에서 비교, 졌으면 그대로, 이겼으면 교체 후 옛 직선을 좌우로 재귀.

insert(node, l, r, new_line):
    if l == r:
        if new_line(l) > tree[node](l):
            tree[node] = new_line
        return
    mid = (l + r) / 2
    if new_line(mid) > tree[node](mid):
        swap(tree[node], new_line)
    if new_line(l) > tree[node](l):
        insert(2*node, l, mid, new_line)
    elif new_line(r) > tree[node](r):
        insert(2*node+1, mid+1, r, new_line)

쿼리는 루트부터 리프까지 경로의 노드에 저장된 직선 모두 평가, max.

query(node, l, r, x):
    if l == r:
        return tree[node](x)
    mid = (l + r) / 2
    res = tree[node](x)
    if x <= mid:
        res = max(res, query(2*node, l, mid, x))
    else:
        res = max(res, query(2*node+1, mid+1, r, x))
    return res

좌표 범위 [-10^9, 10^9] 는 좌표 압축 또는 동적 세그트리로 처리.

알고리즘

# 초기화
tree[1..4*MAXN] = -INF 직선

# 직선 추가
insert(node, l, r, new_line):
    if l == r:
        if new_line(l) > tree[node](l):
            tree[node] = new_line
        return
    mid = (l + r) / 2
    if new_line(mid) > tree[node](mid):
        swap(tree[node], new_line)
    if new_line(l) > tree[node](l):
        insert(2*node, l, mid, new_line)
    elif new_line(r) > tree[node](r):
        insert(2*node+1, mid+1, r, new_line)

# 점 쿼리
query(node, l, r, x):
    if l == r:
        return tree[node](x)
    mid = (l + r) / 2
    res = tree[node](x)
    if x <= mid:
        res = max(res, query(2*node, l, mid, x))
    else:
        res = max(res, query(2*node+1, mid+1, r, x))
    return res

구현

// Li Chao Tree: 직선 추가 O(log N), 점 쿼리 O(log N)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll INF = 1e18;
const int MINX = -1e6, MAXX = 1e6;

struct Line {
  ll a, b;   // y = a*x + b
  ll eval(ll x) const { return a * x + b; }
};

Line tree[4 * (MAXX - MINX + 1)];

void init() {
  for (auto& L : tree) L = {0, -INF};
}

void insert(int node, int l, int r, Line newL) {
  if (l == r) {
      if (newL.eval(l) > tree[node].eval(l))
          tree[node] = newL;
      return;
  }
  int mid = (l + r) / 2;
  if (newL.eval(mid) > tree[node].eval(mid))
      swap(tree[node], newL);
  if (newL.eval(l) > tree[node].eval(l))
      insert(2 * node, l, mid, newL);
  else if (newL.eval(r) > tree[node].eval(r))
      insert(2 * node + 1, mid + 1, r, newL);
}

ll query(int node, int l, int r, ll x) {
  if (l == r)
      return tree[node].eval(x);
  int mid = (l + r) / 2;
  ll res = tree[node].eval(x);
  if (x <= mid)
      res = max(res, query(2 * node, l, mid, x));
  else
      res = max(res, query(2 * node + 1, mid + 1, r, x));
  return res;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  init();
  int n; cin >> n;
  while (n--) {
      int t; cin >> t;
      if (t == 1) {
          ll a, b; cin >> a >> b;
          insert(1, MINX, MAXX, {a, b});
      } else {
          ll x; cin >> x;
          ll ans = query(1, MINX, MAXX, x);
          cout << ans << "\n";
      }
  }
}

# Li Chao Tree: 직선 추가 O(log N), 점 쿼리 O(log N)
import sys
input = sys.stdin.readline

INF = 10**18
MINX, MAXX = -10**6, 10**6
SIZE = 4 * (MAXX - MINX + 1)

class Line:
  def __init__(self, a=0, b=-INF):
      self.a = a
      self.b = b
  def eval(self, x):
      return self.a * x + self.b

tree = [Line() for _ in range(SIZE)]

def insert(node, l, r, newL):
  if l == r:
      if newL.eval(l) > tree[node].eval(l):
          tree[node] = newL
      return
  mid = (l + r) // 2
  if newL.eval(mid) > tree[node].eval(mid):
      tree[node], newL = newL, tree[node]
  if newL.eval(l) > tree[node].eval(l):
      insert(2 * node, l, mid, newL)
  elif newL.eval(r) > tree[node].eval(r):
      insert(2 * node + 1, mid + 1, r, newL)

def query(node, l, r, x):
  if l == r:
      return tree[node].eval(x)
  mid = (l + r) // 2
  res = tree[node].eval(x)
  if x <= mid:
      res = max(res, query(2 * node, l, mid, x))
  else:
      res = max(res, query(2 * node + 1, mid + 1, r, x))
  return res

n = int(input())
out = []
for _ in range(n):
  t, *args = map(int, input().split())
  if t == 1:
      a, b = args
      insert(1, MINX, MAXX, Line(a, b))
  else:
      x = args[0]
      out.append(str(query(1, MINX, MAXX, x)))
print("\n".join(out))

// Li Chao Tree: 직선 추가 O(log N), 점 쿼리 O(log N)
import java.util.*;
import java.io.*;
public class Main {
  static final long INF = (long)1e18;
  static final int MINX = -1000000, MAXX = 1000000;
  static final int SIZE = 4 * (MAXX - MINX + 1);

  static class Line {
      long a, b;
      Line(long a, long b) { this.a = a; this.b = b; }
      long eval(long x) { return a * x + b; }
  }

  static Line[] tree = new Line[SIZE];

  static void init() {
      for (int i = 0; i < SIZE; i++) tree[i] = new Line(0, -INF);
  }

  static void insert(int node, int l, int r, Line newL) {
      if (l == r) {
          if (newL.eval(l) > tree[node].eval(l))
              tree[node] = newL;
          return;
      }
      int mid = (l + r) / 2;
      if (newL.eval(mid) > tree[node].eval(mid)) {
          Line tmp = tree[node];
          tree[node] = newL;
          newL = tmp;
      }
      if (newL.eval(l) > tree[node].eval(l))
          insert(2 * node, l, mid, newL);
      else if (newL.eval(r) > tree[node].eval(r))
          insert(2 * node + 1, mid + 1, r, newL);
  }

  static long query(int node, int l, int r, long x) {
      if (l == r)
          return tree[node].eval(x);
      int mid = (l + r) / 2;
      long res = tree[node].eval(x);
      if (x <= mid)
          res = Math.max(res, query(2 * node, l, mid, x));
      else
          res = Math.max(res, query(2 * node + 1, mid + 1, r, x));
      return res;
  }

  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      init();
      int n = Integer.parseInt(br.readLine());
      StringBuilder sb = new StringBuilder();
      while (n-- > 0) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          int t = Integer.parseInt(st.nextToken());
          if (t == 1) {
              long a = Long.parseLong(st.nextToken());
              long b = Long.parseLong(st.nextToken());
              insert(1, MINX, MAXX, new Line(a, b));
          } else {
              long x = Long.parseLong(st.nextToken());
              sb.append(query(1, MINX, MAXX, x)).append('\n');
          }
      }
      System.out.print(sb);
  }
}

stdin

결과

4
3
2

복잡도

항목	값
직선 추가	O(log N) 시간
점 쿼리	O(log N) 시간
공간	O(N) (좌표 범위 N) 또는 O(M log N) (동적 세그트리)
선분 추가	O(log^2 N) (구간 분할 + 각 노드 O(log N))

좌표 범위가 [-10^9, 10^9] 이면 좌표 압축 또는 동적 세그트리. 선분 (일부 구간에만 존재)은 구간 분할 후 각 노드에 삽입, O(log^2 N).

변형 / 활용

1. 최솟값 쿼리

> 비교를 < 로 변경. DP 최적화에서 흔함.

2. 선분 (Segment) 추가

직선 대신 선분 [xl, xr]. 세그트리의 구간 분할 사용, O(log N) 노드에 삽입. 총 O(log^2 N).

3. 동적 세그트리

좌표 범위 [-10^9, 10^9] 를 압축하지 않고 노드 동적 생성. 공간 O(M log N), M = 직선 개수.

4. DP 최적화

CHT가 필요한 DP (예: dp[i] = min(dp[j] + cost(j, i)) 에서 cost가 볼록) 에서 직선 순서 제약 없이 사용 가능.

함정

1. 좌표 범위 오버플로

a * x + b 계산 시 long long 오버플로. 좌표 압축 또는 __int128.

2. 초기 직선

tree 초기화 시 -INF 직선 설정 필수. 빈 노드 접근 시 undefined.

3. mid 계산 정수 나눗셈

(l + r) / 2 에서 음수 좌표일 때 round 방향 주의. C++은 0으로 round.

4. 선분 vs 직선

선분 추가는 O(log^2 N). 직선 O(log N)과 혼동하지 말 것.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 12795	반평면 땅따먹기	-	kokoa-lab
BOJ 12920	평범한 배낭 2	-	kokoa-lab
BOJ 12778	CTP공국으로 이민 가자	-	kokoa-lab

참고

이 글의 용어 (4개)

세그먼트 트리 (Segment Tree)algorithm: 정의 세그먼트 트리 (Segment Tree) 는 배열의 구간 쿼리 (range query) 와 점 갱신 (point update) 를 모두 O(log N) 에 처리하는 이진 트…
CHT (Convex Hull Trick)algorithm: 정의 Convex Hull Trick (CHT) 은 DP 전이 같이 선형식들의 lower envelope (또는 upper envelope) 에서 한 점 값을 평가하는 패턴을, …
DP Optimization: CHT, D&C, Knuth, SMAWKalgorithm: 정의 일반 DP 를 O(N²) 또는 O(N³) 에서 O(N log N) 또는 O(N) 으로 낮추는 여러 최적화 기법의 총칭입니다. 모두 특정 조건 (monotone, concav…
Dynamic Segment Tree: 지연 노드 생성algorithm: 정의 Dynamic Segment Tree 는 값 범위가 매우 크지만 실제 접근 위치가 희소할 때, 필요한 노드만 생성 하는 세그먼트 트리입니다. 공간: O(Q log V), Q…