[JS] 세그먼트 트리

1. 생성하기

class SegmentTree {
  /**
   * @param {number[]} origin
   */
  constructor(origin) {
    const size = origin.length;
    const exp = Math.ceil(Math.log2(size)) + 1;
    const nodeCnt = 1 << exp;

    this.origin = origin;
    this.nodes = Array(nodeCnt);

    /**
     * @param {number} node
     * @param {number} start
     * @param {number} end
     */
    const closureInit = (node, start, end) => {
      if (start === end) {
        this.nodes[node] = this.origin[start];
        return;
      }

      const mid = Math.floor((start + end) / 2);
      const left = node * 2;
      const right = node * 2 + 1;

      closureInit(left, start, mid);
      closureInit(right, mid + 1, end);

      this.nodes[node] = this.nodes[left] + this.nodes[right];
    };

    closureInit(1, 0, size - 1);
  }
}

2. 갱신하기

class SegmentTree {
  constructor(origin) {
    // ...
  }
  
  /**
   * @param {number} idx 
   * @param {number} val 
   */
  update(idx, val) {
    const size = this.origin.length;
    if (idx < 0 || idx >= size) return;

    const diff = val - this.origin[idx];
    this.origin[idx] = val;

    /**
     * @param {number} node
     * @param {number} start
     * @param {number} end
     */
    const closureUpdate = (node, start, end) => {
      this.nodes[node] += diff;
      if (start === end) return;

      const mid = Math.floor((start + end) / 2);
      if (idx <= mid) closureUpdate(node * 2, start, mid);
      else closureUpdate(node * 2 + 1, mid + 1, end);
    };

    closureUpdate(1, 0, size - 1);
  }
}

3. 구간 합 구하기

class SegmentTree {
  constructor(origin) {
    // ...
  }
  
  update(idx, val) {
    // ...
  }

  /**
   * @param {number} left
   * @param {number} right
   */
  sum(left, right) {
    const size = this.origin.length;

    /**
     * @param {number} node
     * @param {number} start
     * @param {number} end
     */
    const clouserSum = (node, start, end) => {
      if (left > end || right < start) return 0;
      if (left <= start && end <= right) return this.nodes[node];

      const mid = Math.floor((start + end) / 2);
      const leftSum = clouserSum(node * 2, start, mid);
      const rightSum = clouserSum(node * 2 + 1, mid + 1, end);

      return leftSum + rightSum;
    };

    return clouserSum(1, 0, size - 1);
  }
}