세그먼트트리 썸네일형 리스트형 세그먼트 트리 마주하고 말았다. 세그먼트 트리 세그먼트 트리 구간을 반복해서 2등분 한 뒤 각각의 잘린 구간이 자신의 구간인 대푯값을 저장하고 관리하게 만드는 자료구조 query: O(logN) update: O(logN) query는 정확히는 O(2logN) 레벨당 2개의 노드만 건드리게 된다. 구현 full binary tree 형태를 가지기 때문에 힙처럼 구간의 모든 값을 배열에 저장할 수 있다. 어떤 노드의 번호가 idx면 왼쪽 자식은 2 * idx, 오른쪽 자식은 2 * idx + 1 배열의 크기는 4 * n 이상으로 설정해야 한다 int query(int l, int r, int node, int nodeL, int nodeR) { if (l nodeR) return v[node]; if (nodeL == .. 더보기 이전 1 다음