BIT impl with deno

bit.test.ts

// not tested general Range XXX Query
// tested STATIC Range Quiey

import { assertEquals, assertThrows } from "https://deno.land/std/testing/asserts.ts";
import { BIT } from "./bit.ts";

Deno.test("BIT Test - Update and Query with Initial Values", () => {
  type Abelian = number;
  const identity: Abelian = 0;
  const operation = (a: Abelian, b: Abelian): Abelian => a + b;

  const initVal = [1, 10, 100, 1000, 10000];

  const bit = new BIT<Abelian>(identity, operation, initVal.length);
  initVal.forEach((val, i) => bit.update(i + 1, val));

  type Query = {
    left: number;
    right: number;
  };

  const queries: Query[] = [
    { left: 2, right: 3 },
    { left: 0, right: 3 },
    { left: 2, right: 5 },
    { left: 3, right: 4 },
    { left: 0, right: 5 },
  ];

  const expectedSums = [100, 111, 11100, 1000, 11111];

  queries.forEach(({ left, right }, i) => {
    const sum = bit.query(right) - bit.query(left);
    assertEquals(sum, expectedSums[i], `sum of [${left}, ${right}) should be ${expectedSums[i]}`);
  });
});

Deno.test("BIT Test - Update with Negative Index", () => {
  type Abelian = number;
  const identity: Abelian = 0;
  const operation = (a: Abelian, b: Abelian): Abelian => a + b;
  const initVal = [1, 10, 100, 1000, 10000];
  const bit = new BIT<Abelian>(identity, operation, initVal.length);
  assertThrows(
    () => {
      bit.update(-1, 1);
    },
    Error,
    "Index must be positive"
  );
});

Deno.test("BIT Test - Update with Index Greater than Size", () => {
  type Abelian = number;
  const identity: Abelian = 0;
  const operation = (a: Abelian, b: Abelian): Abelian => a + b;
  const initVal = [1, 10, 100, 1000, 10000];
  const bit = new BIT<Abelian>(identity, operation, initVal.length);
  assertThrows(
    () => {
      bit.update(initVal.length + 100, 1);
    },
    Error,
    "Index must be positive and less than or equal to size"
  );
});

Deno.test("BIT Test - Query with Negative Index", () => {
  type Abelian = number;
  const identity: Abelian = 0;
  const operation = (a: Abelian, b: Abelian): Abelian => a + b;
  const initVal = [1, 10, 100, 1000, 10000];
  const bit = new BIT<Abelian>(identity, operation, initVal.length);
  assertThrows(
    () => {
      bit.query(-1);
    },
    Error,
    "Index must be positive"
  );
});

Deno.test("BIT Test - Query with Index Greater than Size", () => {
  type Abelian = number;
  const identity: Abelian = 0;
  const operation = (a: Abelian, b: Abelian): Abelian => a + b;
  const initVal = [1, 10, 100, 1000, 10000];
  const bit = new BIT<Abelian>(identity, operation, initVal.length);
  assertThrows(
    () => {
      bit.query(initVal.length + 100);
    },
    Error,
    "Index must be positive and less than or equal to size"
  );
});

Deno.test("BIT Test - Update and Query with Multiplication", () => {
  type Abelian = number;
  const identity: Abelian = 1;
  const operation = (a: Abelian, b: Abelian): Abelian => a * b;

  const initVal = [1, 2, 3, 4, 5];

  const bit = new BIT<Abelian>(identity, operation, initVal.length);
  initVal.forEach((val, i) => bit.update(i + 1, val));

  type Query = {
    left: number;
    right: number;
  };

  const queries: Query[] = [
    { left: 2, right: 3 },
    { left: 0, right: 3 },
    { left: 2, right: 5 },
    { left: 3, right: 4 },
    { left: 0, right: 5 },
  ];

  const expectedProducts = [3, 6, 60, 4, 120];

  queries.forEach(({ left, right }, i) => {
    const product = bit.query(right) / bit.query(left);
    assertEquals(product, expectedProducts[i], `product of [${left}, ${right}) should be ${expectedProducts[i]}`);
  });
});

bit.ts

export class BIT<T> {
  private tree: T[];
  private identity: T;
  private operation: (a: T, b: T) => T;

  constructor(identity: T, operation: (a: T, b: T) => T, size: number) {
    if (size <= 0) {
      throw new Error("Size must be positive");
    }
    this.tree = new Array<T>(size + 1).fill(identity);
    this.identity = identity;
    this.operation = operation;
  }

  update(i: number, val: T): void {
    if (i <= 0 || i > this.tree.length) {
      throw new Error("Index must be positive and less than or equal to size");
    }
    while (i < this.tree.length) {
      this.tree[i] = this.operation(this.tree[i], val);
      i += i & -i;
    }
  }

  query(i: number): T {
    let sum = this.identity;
    if (i < 0 || i > this.tree.length) {
      throw new Error("Index must be positive and less than or equal to size");
    }
    while (i > 0) {
      sum = this.operation(sum, this.tree[i]);
      i -= i & -i;
    }
    return sum;
  }
}

deno.jsonc

{
  "tasks": {
    "run": "deno run bit.ts",
    "test": "deno test bit.test.ts"
  }
}