JavaScript 반복형 세그먼트 트리: 구간 합·단일 대입·결합 순서

여기부터는 필요한 기능을 골라 읽는 참고 영역입니다. 새로운 파일로 전체 코드를 실행할 때는 아래 Node.js 실행 안내를 따르세요. 앞쪽의 작은 브라우저 실습과 전체 파일을 한 콘솔에 이어 붙이지 마세요. 기능별 입력 조건과 반환 형식은 아래 설명을 기준으로 합니다.

문제 상황과 API 계약

대시보드에서 구간별 합계를 조회하는 동시에 특정 칸의 값을 새 값으로 교체한다고 합시다. 접두사 합 배열은 한 칸 수정에 뒤쪽 전체를 다시 계산해야 합니다. 세그먼트 트리는 변경한 잎에서 루트까지의 조상만 다시 계산합니다. 합계 외의 결합 연산에도 같은 구간 분해를 재사용한다는 점이 Fenwick Tree와의 선택 기준입니다.

query(left,right)는 [left,right)의 결합 결과이고 set(index,value)는 값을 교체합니다. add가 아닙니다. 기본 combine은 덧셈, identity는 0입니다. 빈 배열과 빈 구간도 허용하며 query(i,i)는 identity를 반환합니다. 배열 길이는 교육용으로 1,000,000 이하로 제한합니다.

일반화하려면 값 집합과 combine, identity가 모노이드를 이뤄야 합니다. 결합 법칙 op(op(a,b),c)=op(a,op(b,c))와 양쪽 항등원 op(e,a)=op(a,e)=a가 필요합니다. 교환 법칙은 필요하지 않습니다. 정수 합계에서는 e=0이고 문자열 연결에서는 e=""입니다. 결합 함수는 인수나 기존 노드를 수정하지 않는 순수 함수여야 합니다.

정확성을 지키는 불변식

base는 n 이상인 가장 작은 2의 거듭제곱입니다. 원본 values[i]는 tree[base+i]에 놓고 나머지 잎은 항등원으로 채웁니다. 각 내부 노드는 왼쪽 자식과 오른쪽 자식을 그 순서로 결합합니다. 따라서 루트는 패딩을 포함해도 실제 배열 전체와 같은 결과를 갖습니다.

조회는 l,r을 잎 위치로 옮긴 뒤 아직 처리하지 않은 [l,r) 영역을 좁힙니다. l이 오른쪽 자식이면 왼쪽 형제가 범위 밖이므로 tree[l]만 받아 l을 하나 늘립니다. r이 홀수이면 r−1이 범위 안의 마지막 왼쪽 자식이므로 먼저 r을 줄이고 그 노드를 받습니다. 나머지는 완전한 형제 쌍이라 부모로 올릴 수 있습니다.

왼쪽에서 고른 블록은 accLeft 뒤에, 오른쪽에서 고른 블록은 accRight 앞에 붙입니다. 둘 다 뒤에 붙이면 합에서는 버그가 숨지만 문자열 연결이나 행렬 곱에서는 순서가 틀어집니다. 반복이 끝나면 미처리 구간이 없으므로 combine(accLeft,accRight)가 원래 순서의 전체 답입니다.

전체 구현과 실행

Node.js 24의 CommonJS 환경을 기준으로 합니다. 아래 전체 코드를 segment-tree.cjs로 저장하고 파일이 있는 폴더에서 node segment-tree.cjs를 실행하세요. 외부 패키지는 필요하지 않습니다. module.exports는 다른 파일에서 가져올 때 사용하며 require.main 조건 안의 호출은 직접 실행할 때만 작동합니다.

class SegmentTree {
  constructor(values, combine = (a, b) => a + b, identity = 0) {
    if (!Array.isArray(values) || values.length > 1_000_000) {
      throw new RangeError('길이 1,000,000 이하 배열이 필요합니다.');
    }
    if (typeof combine !== 'function') throw new TypeError('결합 함수가 필요합니다.');
    this.n = values.length;
    this.combine = combine;
    this.identity = identity;
    this.base = 1;
    while (this.base < this.n) this.base *= 2;
    this.tree = Array(this.base * 2).fill(identity);
    for (let i = 0; i < this.n; i++) this.tree[this.base + i] = values[i];
    for (let i = this.base - 1; i > 0; i--) {
      this.tree[i] = combine(this.tree[i * 2], this.tree[i * 2 + 1]);
    }
  }
  boundary(i) {
    if (!Number.isInteger(i) || i < 0 || i > this.n) throw new RangeError('잘못된 경계입니다.');
  }
  set(index, value) {
    this.boundary(index);
    if (index === this.n) throw new RangeError('갱신 인덱스는 n보다 작아야 합니다.');
    let p = this.base + index;
    this.tree[p] = value;
    while (p > 1) {
      p = Math.floor(p / 2);
      this.tree[p] = this.combine(this.tree[p * 2], this.tree[p * 2 + 1]);
    }
  }
  query(left, right) {
    this.boundary(left);
    this.boundary(right);
    if (left > right) throw new RangeError('left는 right 이하여야 합니다.');
    let l = left + this.base, r = right + this.base;
    let accLeft = this.identity, accRight = this.identity;
    while (l < r) {
      if (l % 2 === 1) accLeft = this.combine(accLeft, this.tree[l++]);
      if (r % 2 === 1) accRight = this.combine(this.tree[--r], accRight);
      l = Math.floor(l / 2);
      r = Math.floor(r / 2);
    }
    return this.combine(accLeft, accRight);
  }
}

module.exports = { SegmentTree };

if (require.main === module) {
  const s = new SegmentTree([4, 2, 7, 1, 3]);
  console.log(s.query(1, 5));
  s.set(2, 5);
  console.log(s.query(1, 5));
}

직접 실행 출력:

13
11

생성자는 잎을 채운 뒤 base−1부터 거꾸로 계산합니다. 두 자식의 결과가 먼저 존재하도록 순서를 잡았으므로 재귀 빌드가 필요 없습니다. set도 잎에 대입한 다음 Math.floor(p/2)로 올라가 두 자식을 다시 결합합니다.

인덱스에는 비트 시프트 대신 나머지와 나눗셈을 써서 32비트 변환을 피했습니다. 그래도 JavaScript 배열과 메모리는 무한하지 않으므로 길이 제한은 유지합니다. 패딩은 identity로 채웠고 fill이 같은 객체 참조를 반복할 수 있으므로 객체 항등원을 쓸 때도 combine이 수정하지 않아야 합니다.

예제는 [1,5) 합 13을 구하고 2번 값을 7에서 5로 대입한 뒤 11을 구합니다. 문자열 버전 new SegmentTree(["a","b","c","d","e"], (a,b)=>a+b, "")에서 query(1,5)는 "bcde"여야 합니다. 이 순서 확인은 합계만 테스트할 때 놓치는 결함을 찾습니다.

상태 변화 따라가기

복잡도와 적용하지 말아야 할 경우

JavaScript 부동소수 덧셈은 일반적으로 결합 법칙이 성립하지 않습니다. 이 합계 예제는 안전한 정수와 모든 부분합의 정확성을 전제로 합니다. 충분조건은 현재 원소들의 절댓값 합이 Number.MAX_SAFE_INTEGER 이하인 것입니다. 소수 금액을 그대로 더해 회계 정확성을 기대하면 안 됩니다.

덧셈만 필요하고 갱신이 증가량으로 주어진다면 Fenwick Tree가 더 작고 단순할 수 있습니다. 갱신이 전혀 없다면 정적 접두사 합이 질의 O(1)로 더 효율적입니다. 이 구조의 일반성 때문에 모든 구간 문제에서 항상 유리한 것은 아닙니다.

구간 전체에 값을 더하는 작업을 set 반복으로 처리하면 원소 수만큼 비용이 늘어납니다. Lazy propagation은 별도의 구현이며 이 코드에는 없습니다. 순서 의존 연산, 큰 문자열, 변경 가능한 객체를 결합할 때는 결합 함수의 비용과 불변성까지 계약에 포함해야 합니다.

연습으로 확인하기

구간 합을 유지하면서 특정 전시실의 예상 인원을 새 값으로 바꿔 보세요. 증가와 대입을 혼동하지 않는지, 오른쪽 경계를 포함하지 않는지 확인합니다.

[창작 문제] 전시실 예상 인원판 교체

LeetCode 307 – Range Sum Query – Mutable — 값 갱신과 구간 합을 연습하는 공식 문제입니다. 원문은 양 끝 포함 구간을 사용하므로 이 글의 반열린 API로 옮길 때 오른쪽 경계를 변환해야 합니다.

공식 자료

공식 자료 확인일: 2026년 9월 10일. 구현은 이 글의 JavaScript 계약에 맞춰 독립적으로 작성했습니다. 다른 언어 라이브러리의 API와 숫자 범위가 그대로 적용되는 것은 아닙니다.

• AtCoder Library 공식 Segtree: 모노이드와 복잡도
• LeetCode 307 – Range Sum Query – Mutable