Coding Interview Patterns Module 30 – Range queries: Fenwick and segment trees
Fenwick trees for prefix sums with updates
A Fenwick tree keeps running totals while values change: both a point update and a range sum take O(log n). Built on a live ticket count, traced and timed.
What you will learn
- Implement a point update and a prefix total with the steps i += i & -i and i -= i & -i
- Answer range totals as the difference of two prefix totals
- Prove that a prefix total adds each value once and that an update reaches every entry that holds it
- Build a Fenwick tree from existing counts in O(n)
- Handle range additions with point or range totals, and find the position of the k-th item
Before you start
What you’ll learn · Before you start
What you will learn
- Implement a point update and a prefix total with the steps i += i & -i and i -= i & -i
- Answer range totals as the difference of two prefix totals
- Prove that a prefix total adds each value once and that an update reaches every entry that holds it
- Build a Fenwick tree from existing counts in O(n)
- Handle range additions with point or range totals, and find the position of the k-th item
Before you start
On this page
A Fenwick tree, also called a binary indexed tree, keeps running totals that stay correct while the values change:
adding to one value and asking for the total of the first r values each take O(log n) steps. A plain array makes the
question cost O(n), and stored prefix sums make the change cost O(n). The tree is an array of n + 1 entries in which
entry i holds the total of the i & -i values that end at position i, a block whose length is the lowest set bit of
i. A prefix total walks down the entries by clearing that bit, a change walks up by adding it, and the total of a
range is two prefix totals subtracted. Here it keeps a stadium’s ticket counts while sales, refunds and questions
arrive.
The problem: tickets sold by section, live
The problem
A stadium sells tickets for n sections, numbered 1 to n around the ground. Write a class SeatCounter with
sell(section, k), which records k more tickets for one section (k is negative for a refund), and
sold(first, last), which returns the tickets sold in sections first to last, both included. Calls arrive in any
order. Limits: 1 ≤ n ≤ 200,000, at most 200,000 calls, and every answer fits in 64 bits.
Three event lists:
- With n = 8:
sell(3, 5),sell(5, 2),sold(1, 4)gives 5;sell(4, 7),sold(3, 5)gives 14; a refundsell(3, -2), thensold(1, 8)gives 12 andsold(6, 8)gives 0. - With n = 1:
sell(1, 4),sold(1, 1)gives 4; aftersell(1, -4)it gives 0. - With n = 5:
sell(5, 1), thensold(5, 5)gives 1 andsold(1, 4)gives 0. The last section is where loops that stop one step early go wrong.
The brute force, and what each choice costs
There are two obvious designs. A plain array of counts makes a sale one write and a question a loop over its sections. Running totals, where cell i holds the tickets of sections 1 to i, make a question two reads and a subtraction, but a sale must rewrite every total from its section to the last. Each design is fast at one operation and slow at the other:
"""The box office two slow ways, with the work counted.
A plain array of counts: a sale writes one cell, a question reads every section of its range.
Running totals: a question reads two totals, a sale rewrites every total from its section to the last.
"""
import random
def make_events(n, m, seed):
"""m events on sections 1..n: about half sales of 1 to 10 tickets, half questions about a random range."""
rng = random.Random(seed)
events = []
for _ in range(m):
if rng.random() < 0.5:
events.append(("sell", rng.randint(1, n), rng.randint(1, 10)))
else:
a, b = rng.randint(1, n), rng.randint(1, n)
events.append(("sold", min(a, b), max(a, b)))
return events
def plain_array(n, events):
count = [0] * (n + 1) # count[s] = tickets of section s; count[0] is unused
answers, work = [], 0
for kind, x, y in events:
if kind == "sell":
count[x] += y
work += 1
else:
answers.append(sum(count[x : y + 1]))
work += y - x + 1
return answers, work
def running_totals(n, events):
total = [0] * (n + 1) # total[i] = tickets of sections 1..i; total[0] = 0
answers, work = [], 0
for kind, x, y in events:
if kind == "sell":
for i in range(x, n + 1):
total[i] += y
work += n - x + 1
else:
answers.append(total[y] - total[x - 1])
work += 2
return answers, work
print("sections = events plain array (reads + writes) running totals (reads + writes)")
last = None
for n in (1_000, 2_000, 4_000):
events = make_events(n, n, seed=n)
a, work_a = plain_array(n, events)
b, work_b = running_totals(n, events)
assert a == b, "the two brute forces disagree"
grow = "" if last is None else f" x{work_a / last[0]:.1f} and x{work_b / last[1]:.1f}"
print(f"{n:>17,} {work_a:>27,} {work_b:>30,}{grow}")
last = (work_a, work_b)
scale = (200_000 / 4_000) ** 2
print(f"Doubling both sizes multiplies the work by about 4. At 200,000 sections and 200,000 events, about")
print(f"{last[0] * scale:.1e} cells for the plain array and {last[1] * scale:.1e} for the running totals (estimated).")Output
sections = events plain array (reads + writes) running totals (reads + writes)
1,000 172,453 231,429
2,000 639,277 1,041,646 x3.7 and x4.5
4,000 2,682,525 4,004,397 x4.2 and x3.8
Doubling both sizes multiplies the work by about 4. At 200,000 sections and 200,000 events, about
6.7e+09 cells for the plain array and 1.0e+10 for the running totals (estimated).
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 brute_force.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Doubling the sections and the events multiplies the work by about 4, the mark of O(n × m). A random question covers about a third of the sections and a random sale rewrites about half the totals, so at the limits the plain array touches about 6.7 × 10⁹ cells and the running totals about 10¹⁰, far beyond a time limit of a second or two in any language.
The key idea: entries that own blocks of i & −i sections
Write the entry number in binary. Its lowest set bit, i & -i, is the length of the block that entry i totals: 1
for odd i, 2 for 6 (110), 4 for 12 (1100), 8 for 8. Each block ends at its own entry, so entry 12 totals sections
9 to 12, and entry 8 totals 1 to 8.
The block each entry totals, for 16 sections
Text description of the diagram
Sixteen sections are numbered 1 to 16 along the bottom. Above them, each entry of the tree is drawn as a bar over the sections it totals, in five rows by the length of its block.
- The top row holds entry 16, which totals sections 1 to 16.
- The second row holds entry 8, sections 1 to 8.
- The third row holds entries 4 (sections 1 to 4) and 12 (sections 9 to 12).
- The fourth row holds entries 2, 6, 10 and 14, each over two sections: 1 and 2, 5 and 6, 9 and 10, 13 and 14.
- The bottom row holds the odd entries 1, 3, 5 and so on to 15, each over its own section.
Three bars are shaded: entries 13, 12 and 8. Side by side they cover sections 1 to 13 exactly once, so the total of sections 1 to 13 adds those three entries. Four bars have a dashed outline: entries 5, 6, 8 and 16, the only bars that lie over section 5, so a sale in section 5 adds to those four. Entry 8 is both shaded and dashed.
- A question about sections 1 to r adds the entries r, r − (r & −r) and so on until it reaches 0. Each step clears the lowest set bit of the index, so the blocks sit side by side from r down to 1, with no gap and no overlap: 13 (1101) reads 13, then 12 (1100), then 8 (1000).
- A sale in section s adds k to the entries s, s + (s & −s) and so on while they are at most n. Each step adds the lowest set bit, which moves to the next larger block that still contains s: 5, 6, 8 and 16.
- A range from first to last is the total up to last minus the total up to first − 1.
Both loops change one bit position per step and the index never has more than about log₂ n bits, so each loop runs
at most about log₂ n + 1 times. The tree keeps n + 1 numbers, and entry 0 is never used: the loops stop there,
because 0 & -0 is 0.
The loops stretch to three more shapes. A tree over the differences between neighbouring sections adds to a whole range of sections at once. A second such tree also gives totals of ranges after those additions. And a walk down the blocks finds the section that holds the k-th ticket sold.
A dry run: one question, one sale and the example
The program prints every entry’s block for 16 sections, the two paths of the diagram in binary, the first event list step by step, and how many entries the loops visit at n = 200,000:
"""A Fenwick tree over 16 sections: the sections each entry totals, and the entries that a question and a sale
visit. Entry i totals the lowbit(i) = i & -i sections that end at section i."""
def lowbit(i):
return i & -i
def question_path(r):
"""The entries whose blocks, put side by side, are sections 1..r."""
path = []
while r > 0:
path.append(r)
r -= lowbit(r) # drop the lowest set bit
return path
def sale_path(s, n):
"""The entries whose blocks contain section s."""
path = []
while s <= n:
path.append(s)
s += lowbit(s) # carry into the next higher block
return path
n = 16
print("entry bits lowbit sections it totals")
for i in range(1, n + 1):
first = i - lowbit(i) + 1
print(f"{i:5} {i:05b} {lowbit(i):6} {first}..{i}" if first < i else f"{i:5} {i:05b} {lowbit(i):6} {i}")
path = question_path(13)
print("\nSections 1..13 read entries", path, "=", " + ".join(f"[{i - lowbit(i) + 1}..{i}]" for i in reversed(path)))
print(" in bits:", " -> ".join(f"{i:05b}" for i in path), "(each step drops the lowest 1)")
path = sale_path(5, n)
print("A sale in section 5 adds to entries", path)
print(" in bits:", " -> ".join(f"{i:05b}" for i in path), "(each step adds the lowest 1)")
holders = [i for i in range(1, n + 1) if i - lowbit(i) + 1 <= 5 <= i]
print(" the entries whose blocks hold section 5, checked one by one:", holders)
# The example of the lesson: 8 sections, sales (with one refund) and questions.
n = 8
tree = [0] * (n + 1) # tree[0] is never used
events = [("sell", 3, 5), ("sell", 5, 2), ("sold", 1, 4), ("sell", 4, 7), ("sold", 3, 5),
("sell", 3, -2), ("sold", 1, 8), ("sold", 6, 8)]
print("\nThe example on 8 sections:")
for kind, x, y in events:
if kind == "sell":
for i in sale_path(x, n):
tree[i] += y
print(f" sell({x}, {y}): entries {sale_path(x, n)} change; tree[1..8] = {tree[1:]}")
else:
upto_last = sum(tree[i] for i in question_path(y))
before_first = sum(tree[i] for i in question_path(x - 1))
print(f" sold({x}, {y}) = {upto_last} - {before_first} = {upto_last - before_first}"
f" (entries {question_path(y)} minus entries {question_path(x - 1)})")
# How many entries one question or one sale visits at the problem's largest size.
n = 200_000
q = [len(question_path(r)) for r in range(1, n + 1)]
s = [len(sale_path(i, n)) for i in range(1, n + 1)]
print(f"\nAt n = {n:,}: a prefix of sections 1..r reads {sum(q) / n:.1f} entries on average, at most {max(q)};")
print(f"a sale writes {sum(s) / n:.1f} entries on average, at most {max(s)}.")Output
entry bits lowbit sections it totals
1 00001 1 1
2 00010 2 1..2
3 00011 1 3
4 00100 4 1..4
5 00101 1 5
6 00110 2 5..6
7 00111 1 7
8 01000 8 1..8
9 01001 1 9
10 01010 2 9..10
11 01011 1 11
12 01100 4 9..12
13 01101 1 13
14 01110 2 13..14
15 01111 1 15
16 10000 16 1..16
Sections 1..13 read entries [13, 12, 8] = [1..8] + [9..12] + [13..13]
in bits: 01101 -> 01100 -> 01000 (each step drops the lowest 1)
A sale in section 5 adds to entries [5, 6, 8, 16]
in bits: 00101 -> 00110 -> 01000 -> 10000 (each step adds the lowest 1)
the entries whose blocks hold section 5, checked one by one: [5, 6, 8, 16]
The example on 8 sections:
sell(3, 5): entries [3, 4, 8] change; tree[1..8] = [0, 0, 5, 5, 0, 0, 0, 5]
sell(5, 2): entries [5, 6, 8] change; tree[1..8] = [0, 0, 5, 5, 2, 2, 0, 7]
sold(1, 4) = 5 - 0 = 5 (entries [4] minus entries [])
sell(4, 7): entries [4, 8] change; tree[1..8] = [0, 0, 5, 12, 2, 2, 0, 14]
sold(3, 5) = 14 - 0 = 14 (entries [5, 4] minus entries [2])
sell(3, -2): entries [3, 4, 8] change; tree[1..8] = [0, 0, 3, 10, 2, 2, 0, 12]
sold(1, 8) = 12 - 0 = 12 (entries [8] minus entries [])
sold(6, 8) = 12 - 12 = 0 (entries [8] minus entries [5, 4])
At n = 200,000: a prefix of sections 1..r reads 8.7 entries on average, at most 17;
a sale writes 9.3 entries on average, at most 18.
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 paths.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
In the example, sold(3, 5) reads entries 5 and 4, sections 1 to 5, and subtracts entry 2, sections 1 and 2.
At n = 200,000 a prefix total read 8.7 entries on average and never more than 17, and a sale wrote 9.3 on average and
never more than 18: about 17 entries for a range question, against tens of thousands of cells for a slow design.
The cost
| Operation | Time | Extra space |
|---|---|---|
| Plain array of counts | sell O(1), sold O(n) | O(n) |
| Running totals | sell O(n), sold O(1) | O(n) |
| Fenwick tree | sell O(log n), sold O(log n) | O(n) |
Exercise
Exercise · Medium · Python, JavaScript
A live count of tickets by section
A stadium sells tickets for n sections, numbered 1 to n. Write a class SeatCounter with:
SeatCounter(n)(new SeatCounter(n)in JavaScript): every section starts with 0 tickets sold;sell(section, k):kmore tickets are sold in one section;kmay be negative, a refund of tickets sold earlier;sold(first, last): the number of tickets sold in sectionsfirsttolast, both included.
counter = SeatCounter(8)
counter.sell(3, 5)
counter.sell(5, 2)
counter.sold(1, 4) # 5
counter.sell(4, 7)
counter.sold(3, 5) # 14
counter.sell(3, -2) # a refund of 2 tickets in section 3
counter.sold(1, 8) # 12Both methods must take O(log n) time. One sample test makes 100,000 calls on 100,000 sections, which a loop over the sections of every question cannot finish in time. Limits: 1 ≤ n ≤ 200,000 and 1 ≤ first ≤ last ≤ n.
Python · Starter code · seats.py
class SeatCounter:
"""Tickets sold per section, for sections 1 to n."""
def __init__(self, n):
self.n = n
def sell(self, section, k):
"""k more tickets sold in one section (k < 0 for a refund)."""
# Replace this line with your code.
def sold(self, first, last):
"""Tickets sold in sections first to last, both included."""
return 0The sample tests · test_seats.py
import random
from seats import SeatCounter
def lcg(seed):
while True:
seed = seed * 48271 % 2147483647
yield seed
def test_example():
"""the example of the prompt: 5, 14, 12, then 0 for sections 6 to 8"""
c = SeatCounter(8)
c.sell(3, 5)
c.sell(5, 2)
assert c.sold(1, 4) == 5
c.sell(4, 7)
assert c.sold(3, 5) == 14
c.sell(3, -2)
assert c.sold(1, 8) == 12
assert c.sold(6, 8) == 0
def test_one_section():
"""one section: a sale, then a refund of all of it"""
c = SeatCounter(1)
c.sell(1, 4)
assert c.sold(1, 1) == 4
c.sell(1, -4)
assert c.sold(1, 1) == 0
def test_last_section():
"""a sale in section n is counted, and only there"""
c = SeatCounter(5)
c.sell(5, 1)
assert c.sold(5, 5) == 1
assert c.sold(1, 4) == 0
assert c.sold(1, 5) == 1
def test_sixteen_sections():
"""16 sections: entry 16 totals all of them"""
c = SeatCounter(16)
c.sell(5, 3)
c.sell(16, 2)
c.sell(9, 1)
assert c.sold(1, 16) == 6
assert c.sold(9, 16) == 3
assert c.sold(6, 15) == 1
assert c.sold(5, 5) == 3
def test_random_against_plain_array():
"""300 random event lists on 1 to 12 sections, refunds included, against a plain array"""
rng = random.Random(1994)
for trial in range(300):
n = rng.randint(1, 12)
c, plain = SeatCounter(n), [0] * (n + 1)
for _ in range(rng.randint(1, 15)):
if rng.random() < 0.5:
s, k = rng.randint(1, n), rng.randint(-5, 9)
c.sell(s, k)
plain[s] += k
else:
first = rng.randint(1, n)
last = rng.randint(first, n)
assert c.sold(first, last) == sum(plain[first : last + 1]), f"trial {trial}: sold({first}, {last})"
def test_hundred_thousand_events():
"""100,000 sections and 100,000 calls: a loop over every question's sections is too slow"""
n, gen = 100_000, lcg(2026)
c, total, count, last_answer = SeatCounter(n), 0, 0, None
for _ in range(100_000):
if next(gen) % 2 == 0:
c.sell(next(gen) % n + 1, next(gen) % 10 + 1)
else:
a, b = next(gen) % n + 1, next(gen) % n + 1
last_answer = c.sold(min(a, b), max(a, b))
total += last_answer
count += 1
assert (count, total, last_answer) == (50_132, 2_313_273_475, 112_958)JavaScript · Starter code · seats.mjs
/** Tickets sold per section, for sections 1 to n. */
export class SeatCounter {
constructor(n) {
this.n = n;
}
/** k more tickets sold in one section (k < 0 for a refund). */
sell(section, k) {
// Replace this line with your code.
}
/** Tickets sold in sections first to last, both included. */
sold(first, last) {
return 0;
}
}The sample tests · seats.test.mjs
import { test, assert } from 'mysmartcopilot:test';
import { SeatCounter } from './seats.mjs';
let seed = 1994;
const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
const randInt = (lo, hi) => lo + Math.floor(random() * (hi - lo + 1));
test('the example of the prompt: 5, 14, 12, then 0 for sections 6 to 8', () => {
const c = new SeatCounter(8);
c.sell(3, 5);
c.sell(5, 2);
assert.equal(c.sold(1, 4), 5);
c.sell(4, 7);
assert.equal(c.sold(3, 5), 14);
c.sell(3, -2);
assert.equal(c.sold(1, 8), 12);
assert.equal(c.sold(6, 8), 0);
});
test('one section: a sale, then a refund of all of it', () => {
const c = new SeatCounter(1);
c.sell(1, 4);
assert.equal(c.sold(1, 1), 4);
c.sell(1, -4);
assert.equal(c.sold(1, 1), 0);
});
test('a sale in section n is counted, and only there', () => {
const c = new SeatCounter(5);
c.sell(5, 1);
assert.equal(c.sold(5, 5), 1);
assert.equal(c.sold(1, 4), 0);
assert.equal(c.sold(1, 5), 1);
});
test('16 sections: entry 16 totals all of them', () => {
const c = new SeatCounter(16);
c.sell(5, 3);
c.sell(16, 2);
c.sell(9, 1);
assert.equal(c.sold(1, 16), 6);
assert.equal(c.sold(9, 16), 3);
assert.equal(c.sold(6, 15), 1);
assert.equal(c.sold(5, 5), 3);
});
test('300 random event lists on 1 to 12 sections, refunds included, against a plain array', () => {
for (let trial = 0; trial < 300; trial++) {
const n = randInt(1, 12);
const c = new SeatCounter(n);
const plain = new Array(n + 1).fill(0);
const events = randInt(1, 15);
for (let e = 0; e < events; e++) {
if (random() < 0.5) {
const s = randInt(1, n);
const k = randInt(-5, 9);
c.sell(s, k);
plain[s] += k;
} else {
const first = randInt(1, n);
const last = randInt(first, n);
let want = 0;
for (let s = first; s <= last; s++) want += plain[s];
assert.equal(c.sold(first, last), want, `trial ${trial}: sold(${first}, ${last})`);
}
}
}
});
test('100,000 sections and 100,000 calls: a loop over every question\'s sections is too slow', () => {
const n = 100000;
let s = 2026;
const next = () => (s = (s * 48271) % 2147483647);
const c = new SeatCounter(n);
let total = 0;
let count = 0;
let lastAnswer = null;
for (let e = 0; e < 100000; e++) {
if (next() % 2 === 0) {
c.sell((next() % n) + 1, (next() % 10) + 1);
} else {
const a = (next() % n) + 1;
const b = (next() % n) + 1;
lastAnswer = c.sold(Math.min(a, b), Math.max(a, b));
total += lastAnswer;
count += 1;
}
}
assert.deepEqual([count, total, lastAnswer], [50132, 2313273475, 112958]);
});A hint
Entry i of a Fenwick tree totals the i & -i sections that end at section i. Which entries does a sale in section s change, and which entries add up to sections 1 to r? sold(first, last) is then the difference of two such totals.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide, QuickJS): nothing is sent to mysmartcopilot.com. The first run of each language downloads it: Python (about 13.5 MB) or JavaScript (about 0.6 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Check yourself
5 questions about this lesson. Every answer and why it is right is on the page, behind “Show the answer”. Your score stays in this browser.
SeatCounter in five languages, proved and checked Pro: opens with a Pro, Premium or Ultimate pass
Two four-line loops are easy to write and easy to get subtly wrong. This part proves why each one is right, gives the class in Python, JavaScript, Java, C++ and Go with what each printed, builds the tree from existing counts in O(n), and checks it against a plain array on 3,000 random event lists.
In this part:
- Why a prefix total counts each section once: the proof
- Why a sale reaches every entry that holds its section, and no other: the proof
- SeatCounter in five languages
- Building from existing counts in O(n)
- Checked against a plain array on 3,000 random lists
4 runnable examples (C++, Go, Java, JavaScript, Python) · about 4 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Seven bugs reproduced, and the box office timed Pro: opens with a Pro, Premium or Ultimate pass
Most Fenwick bugs come from where the indices start and where the loops stop. The drill runs seven plausible bugs against the correct class until each one gives a wrong answer, and a timed run shows what O(log n) is worth at 200,000 events.
In this part:
- Seven bugs and the smallest input that breaks each: a drill
- Measured: 200,000 events in CPython
- Edge cases worth a test each
2 runnable examples (Python) · about 3 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Range additions, range totals and the k-th ticket Pro: opens with a Pro, Premium or Ultimate pass
Three variations ask for more than point updates and range totals, and each keeps O(log n) an operation with the same two loops. All three are checked against a plain array or a binary search, and a practice set follows.
In this part:
- Complimentary passes: add to a range, read one section
- Add to a range and total a range, with two trees: the algebra
- Which section holds ticket k: walking down the blocks, with numbers
- A practice set with sample answers
- Follow-up questions, answered
2 runnable examples (Python) · about 3 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Interview questions
-
Fresher to mid · Warm-up
What does entry i of a Fenwick tree hold, and why do its positions count from 1?
Entry i holds the total of a block of values that ends at position i and is i & −i long, the value of the lowest set bit of i. Entry 12, 1100 in binary, totals positions 9 to 12, and every odd entry holds a single value. A prefix total up to r adds the entries r, r − (r & −r) and so on, clearing one set bit at each step, and a change at position s adds to the entries s, s + (s & −s) and so on while they exist. Positions count from 1 because both steps need an index with a set bit: 0 & −0 is 0, so a change at index 0 would add to entry 0 forever. Input numbered from 0 is shifted by one, once, where it enters the class.
-
Mid to senior
Tickets are numbered in section order across 200,000 sections, and sales and refunds keep arriving. A lucky-draw screen must show, many times a second, which section holds ticket number k. How do you answer each request in O(log n), and what could break it?
-
Mid to senior
A sponsor adds k passes to every section from l to r, 100,000 times a day, and auditors ask for the total passes in any range of sections, also 100,000 times a day. There are 200,000 sections. Which structure do you build, and what does each operation cost?
-
Senior to staff
A booking map has 2,000 rows of 2,000 seats. Bookings and cancellations change one seat at a time, about a million a day, and a dashboard asks how many seats are booked in any rectangle of rows and seats. What do you build, how much memory does it take, and what does a query cost?
Key takeaways
- Entry i of a Fenwick tree totals the
i & -ivalues that end at position i, counting positions from 1. - A prefix total clears the lowest set bit at each step, a change adds it; both take at most about log₂ n + 1 steps.
- A range total is the prefix up to last minus the prefix up to first − 1.
- At 200,000 events, about 17 entries a question replace tens of thousands of cells for a plain array or stored prefix sums.
References
- A New Data Structure for Cumulative Frequency Tables (P. M. Fenwick, Software: Practice and Experience 24(3), pages 327–336) (John Wiley & Sons)
- Bitwise operations on integer types (The Python Standard Library: built-in types) (Python Software Foundation)
- time.process_time() (The Python Standard Library) (Python Software Foundation)
- Bitwise AND (&) (JavaScript reference) (MDN Web Docs)
- Number.MAX_SAFE_INTEGER (JavaScript reference) (MDN Web Docs)
- The Java Language Specification, Java SE 25: 4.2.2 Integer Operations (Oracle)
- JEP 330: Launch Single-File Source-Code Programs (OpenJDK)
- Working Draft, Programming Languages: C++ (N4950), 7.1 [expr.pre] (ISO/IEC JTC1/SC22/WG21)
- The Go Programming Language Specification: Integer overflow (The Go Authors)
- AddressSanitizer (Clang documentation) (LLVM Project)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress