// fast 2D submatrix sum using cumulative sum algorithm

class Cumsum {
  private cumsum: number[][];

  constructor(data: ArrayLike<number>, width: number, height: number) {
    this.cumsum = [];

    for (let j = 0; j < height; j++) {
      this.cumsum.push([]);
      for (let i = 0; i < width; i++) {
        this.cumsum[j].push(0);
      }
    }

    this.cumsum[0][0] = data[0];

    for (let i = 1; i < width; i++) {
      this.cumsum[0][i] = this.cumsum[0][i - 1] + data[i];
    }

    for (let j = 1; j < height; j++) {
      this.cumsum[j][0] = this.cumsum[j - 1][0] + data[j * width];
    }

    for (let j = 1; j < height; j++) {
      for (let i = 1; i < width; i++) {
        this.cumsum[j][i] =
          data[j * width + i] +
          this.cumsum[j - 1][i] +
          this.cumsum[j][i - 1] -
          this.cumsum[j - 1][i - 1];
      }
    }
  }

  query(x1: number, y1: number, x2: number, y2: number) {
    let ret = this.cumsum[y2][x2];

    if (y1 > 0) ret -= this.cumsum[y1 - 1][x2];
    if (x1 > 0) ret -= this.cumsum[y2][x1 - 1];
    if (x1 > 0 && y1 > 0) ret += this.cumsum[y1 - 1][x1 - 1];

    return ret;
  }
}

export default Cumsum;