구간을 두 부분으로 나누기
루트는 배열 전체 구간을 담당하고 자식들은 그 구간의 왼쪽과 오른쪽 절반을 담당한다. 원소 하나만 남을 때까지 나누면 잎에 도달한다. 부모에는 두 자식의 정보를 합친 결과를 저장한다. 합을 관리한다면 부모 값은 두 자식 값의 합이다.
질의 구간에 필요한 노드
질의 구간에 완전히 포함된 노드는 저장값을 그대로 사용한다. 전혀 겹치지 않는 노드는 제외하고, 일부만 겹치면 자식으로 내려간다. 선택된 노드들이 담당하는 구간을 결합해 답을 얻으므로 각 원소를 하나씩 읽지 않고도 구간 정보를 구할 수 있다.
원소 하나가 바뀌는 경우
원소 하나의 값이 바뀌면 해당 잎과 그 잎에서 루트로 이어지는 조상들의 정보를 다시 계산한다. 예를 들어 합을 저장할 때 3번 원소만 바뀌면 그 원소를 포함하지 않는 다른 가지는 그대로 사용할 수 있다. 트리 높이가 O(log n)이므로 점 갱신도 O(log n)에 처리한다.
연산과 확장 조건
구간 정보를 안정적으로 결합하려면 결합 순서에 따른 성질을 살펴야 한다. 합, 최솟값, 최댓값은 대표적인 예다. 구간 전체를 바꾸는 갱신은 단순한 점 갱신 구현만으로 빠르게 처리되지 않으며 지연 전파 같은 확장이 필요하다. 또한 모든 연산과 모든 확장에서 같은 시간 및 공간 복잡도가 유지되는 것은 아니다.