SegmenTree sum, avg, min , max

SegmenTree.js

class SegmentTree {
  constructor(arr) {
    this.n = arr.length;
    this.treeSum = Array(4 * this.n).fill(0);
    this.treeMin = Array(4 * this.n).fill(Infinity);
    this.treeMax = Array(4 * this.n).fill(-Infinity);
    this.build(arr, 0, 0, this.n - 1);
  }

  build(arr, node, start, end) {
    if (start === end) {
      this.treeSum[node] = arr[start];
      this.treeMin[node] = arr[start];
      this.treeMax[node] = arr[start];
    } else {
      const mid = Math.floor((start + end) / 2);
      this.build(arr, 2 * node + 1, start, mid);
      this.build(arr, 2 * node + 2, mid + 1, end);
      this.treeSum[node] = this.treeSum[2 * node + 1] + this.treeSum[2 * node + 2];
      this.treeMin[node] = Math.min(this.treeMin[2 * node + 1], this.treeMin[2 * node + 2]);
      this.treeMax[node] = Math.max(this.treeMax[2 * node + 1], this.treeMax[2 * node + 2]);
    }
  }

  update(index, value, node = 0, start = 0, end = this.n - 1) {
    if (start === end) {
      this.treeSum[node] = value;
      this.treeMin[node] = value;
      this.treeMax[node] = value;
    } else {
      const mid = Math.floor((start + end) / 2);
      if (start <= index && index <= mid) {
        this.update(index, value, 2 * node + 1, start, mid);
      } else {
        this.update(index, value, 2 * node + 2, mid + 1, end);
      }
      this.treeSum[node] = this.treeSum[2 * node + 1] + this.treeSum[2 * node + 2];
      this.treeMin[node] = Math.min(this.treeMin[2 * node + 1], this.treeMin[2 * node + 2]);
      this.treeMax[node] = Math.max(this.treeMax[2 * node + 1], this.treeMax[2 * node + 2]);
    }
  }

  querySum(l, r, node = 0, start = 0, end = this.n - 1) {
    if (r < start || end < l) {
      return 0;
    }
    if (l <= start && end <= r) {
      return this.treeSum[node];
    }
    const mid = Math.floor((start + end) / 2);
    const leftSum = this.querySum(l, r, 2 * node + 1, start, mid);
    const rightSum = this.querySum(l, r, 2 * node + 2, mid + 1, end);
    return leftSum + rightSum;
  }

  queryMin(l, r, node = 0, start = 0, end = this.n - 1) {
    if (r < start || end < l) {
      return Infinity;
    }
    if (l <= start && end <= r) {
      return this.treeMin[node];
    }
    const mid = Math.floor((start + end) / 2);
    const leftMin = this.queryMin(l, r, 2 * node + 1, start, mid);
    const rightMin = this.queryMin(l, r, 2 * node + 2, mid + 1, end);
    return Math.min(leftMin, rightMin);
  }

  queryMax(l, r, node = 0, start = 0, end = this.n - 1) {
    if (r < start || end < l) {
      return -Infinity;
    }
    if (l <= start && end <= r) {
      return this.treeMax[node];
    }
    const mid = Math.floor((start + end) / 2);
    const leftMax = this.queryMax(l, r, 2 * node + 1, start, mid);
    const rightMax = this.queryMax(l, r, 2 * node + 2, mid + 1, end);
    return Math.max(leftMax, rightMax);
  }

  queryAvg(l, r) {
    const sum = this.querySum(l, r);
    const count = r - l + 1;
    return count > 0 ? sum / count : 0; // Handle division by zero
  }
}

// Example usage
const arr = [1, 3, 5, 7, 9, 11];
const segTree = new SegmentTree(arr);

console.log(segTree.querySum(1, 3)); // Output: 15 (sum of elements from index 1 to 3)
console.log(segTree.queryMin(1, 3)); // Output: 3 (min value from index 1 to 3)
console.log(segTree.queryMax(1, 3)); // Output: 7 (max value from index 1 to 3)
console.log(segTree.queryAvg(1, 3)); // Output: 5 (average value from index 1 to 3)
segTree.update(1, 10);
console.log(segTree.querySum(1, 3)); // Output: 22 (sum of elements from index 1 to 3 after update)
console.log(segTree.queryMin(1, 3)); // Output: 5 (min value from index 1 to 3 after update)
console.log(segTree.queryMax(1, 3)); // Output: 10 (max value from index 1 to 3 after update)
console.log(segTree.queryAvg(1, 3)); // Output: 7.333 (average value from index 1 to 3 after update)