/**
 * 线段树类
 * @param {number[]} nums
 */
var SeqTree = function (nums) {
  this.nums = nums;
  this.tree = new Array(4 * nums.length).fill(0);
  this.build(0, 0, nums.length - 1);
};

/**
 * 建树方法
 * @param {*} node 当前树节点
 * @param {*} start 当前树节点涵盖范围的起点
 * @param {*} end 当前树节点涵盖范围的终点
 * @return {void}
 */
SeqTree.prototype.build = function (node, start, end) {
  if (start === end) {
    this.tree[node] = this.nums[start];
    return;
  }
  const mid = start + Math.floor((end - start) / 2);
  const leftNode = 2 * node + 1;
  const rightNode = 2 * node + 2;
  this.build(leftNode, start, mid);
  this.build(rightNode, mid + 1, end);
  this.tree[node] = this.tree[leftNode] + this.tree[rightNode];
};

/**
 * 对外使用的更新方法
 * @param {number} index 需要修改的节点下标
 * @param {number} val 需要修改的数值
 * @return {void}
 */
SeqTree.prototype.update = function (index, val) {
  this.change(0, 0, this.nums.length - 1, index, val);
};

/**
 * 更新树节点
 * @param {*} node 当前树节点
 * @param {*} start 涵盖范围的起点
 * @param {*} end 涵盖范围的终点
 * @param {*} idx 需要修改的节点下标
 * @param {*} val 需要修改的数值
 * @return {void}
 */
SeqTree.prototype.change = function (node, start, end, idx, val) {
  if (start === end) {
    this.tree[node] = val;
  } else if (idx < start || end < idx) {
    return;
  } else {
    const mid = start + Math.floor((end - start) / 2);
    const leftNode = 2 * node + 1;
    const rightNode = 2 * node + 2;
    if (start <= idx && idx <= mid) {
      this.change(leftNode, start, mid, idx, val);
    } else {
      this.change(rightNode, mid + 1, end, idx, val);
    }
    this.tree[node] = this.tree[leftNode] + this.tree[rightNode];
  }
};

/**
 * 对外使用的区间求和方法
 * @param {number} left 查询区间的左节点
 * @param {number} right 查询区间的右节点
 * @return {number} 返回区间和
 */
SeqTree.prototype.sumRange = function (left, right) {
  return this.query(0, 0, this.nums.length - 1, left, right);
};

/**
 * 查询范围的和
 * @param {*} node 当前树节点
 * @param {*} start 涵盖范围的起点
 * @param {*} end 涵盖范围的终点
 * @param {*} l 查询区间的左节点
 * @param {*} r 查询区间的右节点
 * @return {number} 返回区间和
 */
SeqTree.prototype.query = function (node, start, end, l, r) {
  if (r < start || end < l) {
    return 0;
  } else if (l <= start && end <= r) {
    return this.tree[node];
  } else {
    const mid = start + Math.floor((end - start) / 2);
    const leftNode = 2 * node + 1;
    const rightNode = 2 * node + 2;
    const leftSum = this.query(leftNode, start, mid, l, r);
    const rightSum = this.query(rightNode, mid + 1, end, l, r);
    return leftSum + rightSum;
  }
};

Q.E.D.