Fenwick trees (binary indexed trees)

Python · trace/fenwick.py

"""Booked seats per row of a 16-row theatre (synthetic), kept in a Fenwick tree, with the positions each step uses."""

import random


class Fenwick:
    """Prefix sums of values[1..n] while single values change. tree[0] is never used."""

    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def add(self, i, delta):
        """values[i] += delta: climb to every position whose range contains i."""
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    def prefix(self, i):
        """values[1] + ... + values[i]: descend through ranges that split 1..i without overlap."""
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i
        return total

    def range_sum(self, left, right):
        """values[left] + ... + values[right]."""
        return self.prefix(right) - self.prefix(left - 1)


def climb(i, n):
    path = []
    while i <= n:
        path.append(i)
        i += i & -i
    return path


def descend(i):
    path = []
    while i > 0:
        path.append(i)
        i -= i & -i
    return path


rows = 16
seats = Fenwick(rows)
for row, change in [(5, 4), (12, 2), (3, 3), (11, 1), (5, -1)]:
    seats.add(row, change)
    print(f"row {row:>2} {change:+d} seats: updates positions {climb(row, rows)}")
print("tree[1..16]:", seats.tree[1:])
print(f"rows 1-11: reads positions {descend(11)}, total {seats.prefix(11)}")
print(f"rows 4-12: prefix(12) reads {descend(12)}, prefix(3) reads {descend(3)}, total {seats.range_sum(4, 12)}")

# The same bookings on a plain list, compared on 1,000 random changes and questions.
rng = random.Random(3)
plain = [0] * (rows + 1)
check = Fenwick(rows)
agree = 0
for _ in range(1000):
    row = rng.randint(1, rows)
    change = rng.randint(-2, 5)
    plain[row] += change
    check.add(row, change)
    left = rng.randint(1, rows)
    right = rng.randint(left, rows)
    agree += check.range_sum(left, right) == sum(plain[left : right + 1])
print(f"{agree:,} of 1,000 random range totals agree with a plain list")

row  5 +4 seats: updates positions [5, 6, 8, 16]
row 12 +2 seats: updates positions [12, 16]
row  3 +3 seats: updates positions [3, 4, 8, 16]
row 11 +1 seats: updates positions [11, 12, 16]
row  5 -1 seats: updates positions [5, 6, 8, 16]
tree[1..16]: [0, 0, 3, 3, 3, 3, 0, 6, 0, 0, 1, 3, 0, 0, 0, 9]
rows 1-11: reads positions [11, 10, 8], total 7
rows 4-12: prefix(12) reads [12, 8], prefix(3) reads [3, 2], total 6
1,000 of 1,000 random range totals agree with a plain list

JavaScript · trace/fenwick.mjs

// Booked seats per row of a 16-row theatre (synthetic), kept in a Fenwick tree, with the positions each step uses.

/** Prefix sums of values[1..n] while single values change. tree[0] is never used. */
class Fenwick {
  constructor(n) {
    this.n = n;
    this.tree = new Array(n + 1).fill(0);
  }

  /** values[i] += delta: climb to every position whose range contains i. */
  add(i, delta) {
    for (; i <= this.n; i += i & -i) this.tree[i] += delta;
  }

  /** values[1] + ... + values[i]: descend through ranges that split 1..i without overlap. */
  prefix(i) {
    let total = 0;
    for (; i > 0; i -= i & -i) total += this.tree[i];
    return total;
  }

  /** values[left] + ... + values[right]. */
  rangeSum(left, right) {
    return this.prefix(right) - this.prefix(left - 1);
  }
}

const climb = (i, n) => {
  const path = [];
  for (; i <= n; i += i & -i) path.push(i);
  return path;
};
const descend = (i) => {
  const path = [];
  for (; i > 0; i -= i & -i) path.push(i);
  return path;
};
const list = (a) => `[${a.join(', ')}]`;
/** Digits in groups of three, as Python prints them with a comma format. */
const grouped = (v) => String(v).replace(/\B(?=(\d{3})+(?!\d))/g, ',');

const rows = 16;
const seats = new Fenwick(rows);
for (const [row, change] of [[5, 4], [12, 2], [3, 3], [11, 1], [5, -1]]) {
  seats.add(row, change);
  const sign = change >= 0 ? `+${change}` : `${change}`;
  console.log(`row ${String(row).padStart(2)} ${sign} seats: updates positions ${list(climb(row, rows))}`);
}
console.log(`tree[1..16]: ${list(seats.tree.slice(1))}`);
console.log(`rows 1-11: reads positions ${list(descend(11))}, total ${seats.prefix(11)}`);
console.log(`rows 4-12: prefix(12) reads ${list(descend(12))}, prefix(3) reads ${list(descend(3))}, total ${seats.rangeSum(4, 12)}`);

// The same bookings on a plain array, compared on 1,000 random changes and questions (a seeded generator).
let seed = 3;
const pick = (lo, hi) => {
  seed = (seed * 48271) % 2147483647;
  return lo + (seed % (hi - lo + 1));
};
const plain = new Array(rows + 1).fill(0);
const check = new Fenwick(rows);
let agree = 0;
for (let t = 0; t < 1000; t++) {
  const row = pick(1, rows);
  const change = pick(-2, 5);
  plain[row] += change;
  check.add(row, change);
  const left = pick(1, rows);
  const right = pick(left, rows);
  let total = 0;
  for (let r = left; r <= right; r++) total += plain[r];
  if (check.rangeSum(left, right) === total) agree++;
}
console.log(`${grouped(agree)} of 1,000 random range totals agree with a plain list`);

row  5 +4 seats: updates positions [5, 6, 8, 16]
row 12 +2 seats: updates positions [12, 16]
row  3 +3 seats: updates positions [3, 4, 8, 16]
row 11 +1 seats: updates positions [11, 12, 16]
row  5 -1 seats: updates positions [5, 6, 8, 16]
tree[1..16]: [0, 0, 3, 3, 3, 3, 0, 6, 0, 0, 1, 3, 0, 0, 0, 9]
rows 1-11: reads positions [11, 10, 8], total 7
rows 4-12: prefix(12) reads [12, 8], prefix(3) reads [3, 2], total 6
1,000 of 1,000 random range totals agree with a plain list