///|
/// Fenwick tree over an abelian additive group. Integer arithmetic wraps at its bit width.
pub struct FenwickTree[T] {
  priv data : Array[T]
} derive(Debug)

///|
pub fn[T : @algebra.Zero] FenwickTree::new(n : Int) -> FenwickTree[T] {
  guard n >= 0 && n <= 100000000 else { panic() }
  { data: Array::makei(n, _ => @algebra.Zero::zero()), }
}

///|
/// Adds x at p. O(log n).
pub fn[T : Add] FenwickTree::add(self : FenwickTree[T], p : Int, x : T) -> Unit {
  guard 0 <= p && p < self.data.length() else { panic() }
  let mut i = p + 1
  while i <= self.data.length() {
    self.data[i - 1] = self.data[i - 1] + x
    i += i & -i
  }
}

///|
fn[T : @algebra.Zero + Add] FenwickTree::prefix(
  self : FenwickTree[T],
  r : Int,
) -> T {
  let mut r = r
  let mut result = @algebra.Zero::zero()
  while r > 0 {
    result = result + self.data[r - 1]
    r -= r & -r
  }
  result
}

///|
/// Sum of [l, r). O(log n).
pub fn[T : @algebra.Zero + Add + Sub] FenwickTree::sum(
  self : FenwickTree[T],
  l : Int,
  r : Int,
) -> T {
  guard 0 <= l && l <= r && r <= self.data.length() else { panic() }
  self.prefix(r) - self.prefix(l)
}