可更新数据与求区间和。

    1. var NumArray = function(nums) {
    2.     n = nums.length;
    3.     this.segmentTree = new Array(nums.length * 4).fill(0);
    4.     this.build(0, 0, n - 1, nums);
    5.     console.log(this.segmentTree)
    6. };
    8. NumArray.prototype.update = function(index, val) {
    9.     this.change(index, val, 0, 0, n - 1);
    10. };
    12. NumArray.prototype.sumRange = function(left, right) {
    13.     return this.range(left, right, 0, 0, n - 1);
    14. };
    16. NumArray.prototype.build = function(node, s, e, nums) {
    17.     if (s === e) {
    18.         this.segmentTree[node] = nums[s];
    19.         return;
    20.     }
    21.     const m = s + Math.floor((e - s) / 2);
    22.     this.build(node * 2 + 1, s, m, nums);
    23.     this.build(node * 2 + 2, m + 1, e, nums);
    24.     this.segmentTree[node] = this.segmentTree[node * 2 + 1] + this.segmentTree[node * 2 + 2];
    25. }
    27. NumArray.prototype.change = function(index, val, node, s, e) {
    28.     if (s === e) {
    29.         this.segmentTree[node] = val;
    30.         return;
    31.     }
    32.     const m = s + Math.floor((e - s) / 2);
    33.     if (index <= m) {
    34.         this.change(index, val, node * 2 + 1, s, m);
    35.     } else {
    36.         this.change(index, val, node * 2 + 2, m + 1, e);
    37.     }
    38.     this.segmentTree[node] = this.segmentTree[node * 2 + 1] + this.segmentTree[node * 2 + 2];
    39. }
    41. NumArray.prototype.range = function(left, right, node, s, e) {
    42.     if (left === s && right === e) {
    43.         return this.segmentTree[node];
    44.     }
    45.     const m = s + Math.floor((e - s) / 2);
    46.     if (right <= m) {
    47.         return this.range(left, right, node * 2 + 1, s, m);
    48.     } else if (left > m) {
    49.         return this.range(left, right, node * 2 + 2, m + 1, e);
    50.     } else {
    51.         return this.range(left, m, node * 2 + 1, s, m) + this.range(m + 1, right, node * 2 + 2, m + 1, e);
    52.     }
    53. }