Why this matters when you build with AI
An AI tool will write a Fenwick tree in a few lines, and the code looks right. The bugs are in the index arithmetic. The usual one is a 0-based array: the code starts at index 0, the update loop never moves, and the program runs forever. Another is a tree that works for positive numbers and gives a wrong answer once a value goes negative, because the search for the k-th element depends on a rule that only holds for non-negative counts. Neither bug shows up in a short sample, so you have to test with a brute force.
A Fenwick tree is the right tool when you need a prefix sum after many changes, and a full segment tree would be more code than the problem needs. It is short, fast, and easy to test. It is also limited: it works for operations that can be undone, such as sums and counts, and it does not answer range minimum queries. The segment tree lesson covers those.
Every program in this lesson was compiled with g++ -O2 -std=c++17 on the machine that wrote it, using g++ 15.2.0 (checked with g++ --version). Each structure was checked against a brute force on random small inputs with a fixed seed, and the printed outputs below were copied from those runs. The timing figure is one run on that machine and will differ on yours. No outside source was checked for this lesson, so the statements here come from the code and from the tests.
The idea: a tree of partial sums stored in an array
Take an array a[1..n] of numbers. You want two things: change one value, and ask for the sum of a[1..i]. A plain array gives a fast change and a slow query, since the query adds up i values. A stored prefix table gives a fast query and a slow change, since one change moves every later prefix.
A Fenwick tree (also called a binary indexed tree, or BIT) balances the two. It stores an array t[1..n], where t[i] holds the sum of a fixed block of a that ends at i. The block length is the lowest set bit of i. That is the value i & -i, the largest power of two that divides i.
Worked example with n = 8. Here is each index, its lowest set bit, and the block it covers:
i binary lowbit(i) block of a that t[i] holds
1 0001 1 a[1]
2 0010 2 a[1..2]
3 0011 1 a[3]
4 0100 4 a[1..4]
5 0101 1 a[5]
6 0110 2 a[5..6]
7 0111 1 a[7]
8 1000 8 a[1..8]The block for i starts right after i - lowbit(i) and ends at i. For example, i = 6 has lowbit(6) = 2, so its block is (4, 6], which is a[5] and a[6].
Lowbit navigation: two loops and nothing else
Two loops do all the work. Both move by i & -i.
To read the prefix sum a[1..i], start at i and add t[i]. Then move to i - (i & -i), which removes the lowest set bit, and repeat until the index is 0. Each step removes one set bit, so the loop runs at most as many times as there are bits in i, which is at most about 18 for i up to 200000.
Worked example: the prefix a[1..7] reads t[7], then t[6], then t[4], and then stops at 0. The blocks are a[7], a[5..6] and a[1..4]. Together they cover indices 1 to 7 exactly once.
To change a[i] by a value v, start at i and add v to t[i]. Then move to i + (i & -i), which adds the lowest set bit, and repeat while the index is at most n. Each step goes to the next block that contains i.
Worked example: changing a[3] updates t[3], then t[4], then t[8]. Those are exactly the blocks that contain index 3: a[3], a[1..4] and a[1..8].
Point update and prefix query in C++
The code below is the full file that this lesson was checked with. The first struct is the basic tree. The later structs and the functions are extensions described in the following sections. Read the first struct now, and use the rest when you reach each section.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Fenwick tree over indices 1..n. t[i] stores the sum of a over (i - lowbit(i), i].
struct Fenwick {
int n;
vector<ll> t;
explicit Fenwick(int n) : n(n), t(n + 1, 0) {}
// O(n) build from a[1..n]; a[0] is ignored.
explicit Fenwick(const vector<ll>& a) : n((int)a.size() - 1), t(a) {
t[0] = 0;
for (int i = 1; i <= n; i++) {
int j = i + (i & -i); // parent: the next node that covers i
if (j <= n) t[j] += t[i];
}
}
// a[i] += v
void add(int i, ll v) {
for (; i <= n; i += i & -i) t[i] += v;
}
// sum of a[1..i]
ll prefix(int i) const {
ll s = 0;
for (; i > 0; i -= i & -i) s += t[i];
return s;
}
// sum of a[l..r]
ll range(int l, int r) const { return prefix(r) - prefix(l - 1); }
// Needs a[i] >= 0. Returns the first index p with prefix(p) >= x, or n + 1 if none.
int first_at_least(ll x) const {
int pos = 0;
int step = 1;
while (step * 2 <= n) step *= 2;
for (; step > 0; step >>= 1) {
if (pos + step <= n && t[pos + step] < x) {
pos += step;
x -= t[pos];
}
}
return pos + 1;
}
};
// Range add on a[l..r], point query a[i].
struct RangeAddPointQuery {
Fenwick f;
explicit RangeAddPointQuery(int n) : f(n) {}
void add(int l, int r, ll v) {
f.add(l, v);
f.add(r + 1, -v);
}
ll get(int i) const { return f.prefix(i); }
};
// Range add on a[l..r], range sum on a[l..r]. Two Fenwick trees.
struct RangeAddRangeSum {
int n;
Fenwick b1, b2;
explicit RangeAddRangeSum(int n) : n(n), b1(n), b2(n) {}
void add(int l, int r, ll v) {
b1.add(l, v);
b1.add(r + 1, -v);
b2.add(l, v * (l - 1));
b2.add(r + 1, -v * r);
}
ll prefix(int i) const { return b1.prefix(i) * i - b2.prefix(i); }
ll range(int l, int r) const { return prefix(r) - prefix(l - 1); }
};
// Count pairs i < j with 0 < a[i] - a[j] <= D.
// Scan left to right. For each j, count earlier values in (a[j], a[j] + D].
ll count_close_inversions(const vector<ll>& a, ll D) {
int n = (int)a.size();
vector<ll> vals(a);
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
int m = (int)vals.size();
Fenwick bit(m);
ll total = 0;
for (int j = 0; j < n; j++) {
// 1-based ids: value vals[k] has id k + 1.
int above = int(upper_bound(vals.begin(), vals.end(), a[j]) - vals.begin()); // ids <= above are <= a[j]
int upto = int(upper_bound(vals.begin(), vals.end(), a[j] + D) - vals.begin()); // ids <= upto are <= a[j] + D
if (upto > above) total += bit.prefix(upto) - bit.prefix(above);
int id = int(lower_bound(vals.begin(), vals.end(), a[j]) - vals.begin()) + 1;
bit.add(id, 1);
}
return total;
}
ll brute_close_inversions(const vector<ll>& a, ll D) {
ll total = 0;
int n = (int)a.size();
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (a[i] - a[j] > 0 && a[i] - a[j] <= D) total++;
return total;
}
void demo() {
// Point update and prefix query.
vector<ll> a = {0, 5, 1, 4, 2, 3}; // a[1..5]
Fenwick f(a);
printf("prefix(3)=%lld range(2,4)=%lld\n", f.prefix(3), f.range(2, 4));
f.add(3, 10);
printf("after a[3]+=10: prefix(3)=%lld\n", f.prefix(3));
printf("first index with prefix >= 12: %d\n", f.first_at_least(12));
// Range add, point query.
RangeAddPointQuery rp(5);
rp.add(2, 4, 7);
rp.add(4, 5, -3);
printf("point values:");
for (int i = 1; i <= 5; i++) printf(" %lld", rp.get(i));
printf("\n");
// Range add, range sum.
RangeAddRangeSum rr(5);
rr.add(2, 4, 7);
rr.add(4, 5, -3);
printf("range sums [1,5]=%lld [2,3]=%lld [4,5]=%lld\n", rr.range(1, 5), rr.range(2, 3), rr.range(4, 5));
}
int main(int argc, char** argv) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (argc > 1 && string(argv[1]) == "demo") {
demo();
return 0;
}
if (argc > 1 && string(argv[1]) == "stress") {
mt19937 rng(20261108);
auto rnd = [&](int lo, int hi) { return uniform_int_distribution<int>(lo, hi)(rng); };
// Point update / prefix query / first_at_least.
for (int it = 0; it < 3000; it++) {
int n = rnd(1, 12);
vector<ll> a(n + 1, 0);
for (int i = 1; i <= n; i++) a[i] = rnd(0, 9);
Fenwick f(a);
vector<ll> raw = a;
for (int q = 0; q < 30; q++) {
int op = rnd(0, 2);
if (op == 0) {
int i = rnd(1, n), v = rnd(-5, 9);
if (raw[i] + v < 0) v = -raw[i];
raw[i] += v;
f.add(i, v);
} else if (op == 1) {
int l = rnd(1, n), r = rnd(l, n);
ll s = 0;
for (int i = l; i <= r; i++) s += raw[i];
if (f.range(l, r) != s) { printf("FAIL range\n"); return 1; }
} else {
ll x = rnd(1, 60);
int want = n + 1;
ll run = 0;
for (int i = 1; i <= n; i++) {
run += raw[i];
if (run >= x) { want = i; break; }
}
if (f.first_at_least(x) != want) { printf("FAIL kth\n"); return 1; }
}
}
}
// Range add / range sum and range add / point query.
for (int it = 0; it < 3000; it++) {
int n = rnd(1, 12);
RangeAddRangeSum rr(n);
RangeAddPointQuery rp(n);
vector<ll> raw(n + 1, 0);
for (int q = 0; q < 30; q++) {
if (rnd(0, 1) == 0) {
int l = rnd(1, n), r = rnd(l, n), v = rnd(-9, 9);
rr.add(l, r, v);
rp.add(l, r, v);
for (int i = l; i <= r; i++) raw[i] += v;
} else {
int l = rnd(1, n), r = rnd(l, n);
ll s = 0;
for (int i = l; i <= r; i++) s += raw[i];
if (rr.range(l, r) != s) { printf("FAIL rr\n"); return 1; }
int i = rnd(1, n);
if (rp.get(i) != raw[i]) { printf("FAIL rp\n"); return 1; }
}
}
}
// Close inversions against brute force.
for (int it = 0; it < 3000; it++) {
int n = rnd(0, 15);
vector<ll> a(n);
for (auto& x : a) x = rnd(-6, 6);
ll D = rnd(0, 8);
if (count_close_inversions(a, D) != brute_close_inversions(a, D)) {
printf("FAIL inversions\n");
return 1;
}
}
printf("all stress tests passed\n");
return 0;
}
// Task: first line n and D, second line n values. Print the number of pairs i < j
// with 0 < a[i] - a[j] <= D.
int n;
ll D;
cin >> n >> D;
vector<ll> a(n);
for (auto& x : a) cin >> x;
cout << count_close_inversions(a, D) << "\n";
return 0;
}The Fenwick struct has three methods that do the main work: add, prefix, and range. The constructor that takes a vector builds the tree in O(n), which is described below. Compile the file with g++ -O2 -std=c++17 -o fen fen.cpp, then run ./fen demo to see the output of the examples in this lesson.
Real output of ./fen demo:
prefix(3)=10 range(2,4)=7
after a[3]+=10: prefix(3)=20
first index with prefix >= 12: 3
point values: 0 7 7 4 -3
range sums [1,5]=15 [2,3]=14 [4,5]=1Check the first line by hand. The array is 5, 1, 4, 2, 3, so prefix(3) = 5 + 1 + 4 = 10, and range(2,4) = 1 + 4 + 2 = 7. Those match.
The add loop is the update from the previous section. The prefix loop is the query. Both run in O(log n) steps. The class does not check that i is between 1 and n. Passing 0 is the 0-based bug described under common mistakes.
Building the tree in O(n)
If you know all the values up front, you can build the tree in O(n) time instead of calling add n times, which takes O(n log n). The idea is that each node i only needs to pass its total to its parent, i + lowbit(i). Process the nodes in increasing order. When you reach i, all its children have already added their totals to t[i], so t[i] is complete. Then add it to the parent.
The constructor in the code does exactly that. The line t(a) copies the values first, and the loop then moves each completed node to its parent. The Python section below checks this build against repeated add calls on random arrays, and the two trees match.
Range update with point query
Sometimes the operation is the reverse. You add v to every element of a[l..r], and you ask for one element a[i]. A single Fenwick tree handles this with a difference array. Store d[l] += v and d[r + 1] -= v. The value a[i] is then the prefix sum of d up to i, because the +v at l carries forward until the -v at r + 1 cancels it.
The code RangeAddPointQuery does this. add(l, r, v) makes two point updates on the tree, and get(i) is a prefix query.
Worked example with n = 5. First call rp.add(2, 4, 7). It calls f.add(2, 7) and f.add(5, -7). Second call rp.add(4, 5, -3). It calls f.add(4, -3) and f.add(6, 3). Index 6 is larger than n = 5, so that update does nothing.
The difference array is now d = [0, 7, 0, -3, -7], for indices 1 to 5. The point value at i is the prefix sum of d up to i, which gives 0, 7, 7, 4, -3. That matches the demo output 0 7 7 4 -3.
The point query is the prefix sum of the difference array. An update at r + 1 past n is harmless, because add stops at n.
Range update with range query
Now the hardest common case: add to a range and ask for the sum of a range. A single tree cannot do it, because the sum of a[1..x] depends on where each change started, not just on the total of the changes.
Let d be the difference array as before, so a[i] = d[1] + ... + d[i]. The sum of the first x values is:
S(x) = sum over j from 1 to x of d[j] * (x - j + 1)
Each d[j] is counted once for every i from j to x, and there are x - j + 1 such i. Rewrite that as:
S(x) = x * (sum of d[j] for j <= x) - (sum of d[j] * (j - 1) for j <= x)
So two Fenwick trees are enough. b1 stores d[j] and b2 stores d[j] * (j - 1). The prefix sum is x * b1.prefix(x) - b2.prefix(x).
When you add v to [l, r], the difference array changes at two places: d[l] += v and d[r + 1] -= v. The second tree must store the product with j - 1, so it gets v * (l - 1) at l and -v * r at r + 1, since (r + 1) - 1 = r. The code RangeAddRangeSum::add does exactly these four updates.
Worked check with the same data as before. After the two calls, the range sums printed by the demo are range sums [1,5]=15 [2,3]=14 [4,5]=1. Those match the array 0, 7, 7, 4, -3 from the point query example: 0 + 7 + 7 + 4 - 3 = 15, 7 + 7 = 14, and 4 - 3 = 1.
The price of two trees is double the work and double the memory, which is still O(n). Learners sometimes try to store a[i] itself in the second tree. That is wrong, because the range add would then need to touch every position.
Finding the k-th element by binary descent
Sometimes you do not know the index. You know the total you want to reach and need the first index where the running sum meets it. If the values are counts of something, that is the k-th smallest element.
Since all values are non-negative, the prefix sums never decrease. That makes the search monotone, so you can binary search on the index. The tree allows a faster search that moves down the bits of the index at once. This is called binary descent.
Start with pos = 0 and the largest power of two step that is at most n. At each step, if pos + step is in range and t[pos + step] is less than the target x, then the whole block (pos, pos + step] is too small. Move pos forward, subtract the block sum from x, and continue with the smaller step. At the end, pos + 1 is the answer.
Worked example with a = [5, 1, 4, 2, 3], so n = 5. The tree is t = [_, 5, 6, 4, 12, 3]. The largest power of two at most 5 is 4. Target x = 12:
step = 4:pos + 4 = 4, andt[4] = 12. Is12 < 12? No. Stay atpos = 0.step = 2:pos + 2 = 2, andt[2] = 6. Is6 < 12? Yes. Move topos = 2, and the target becomesx = 12 - 6 = 6.step = 1:pos + 1 = 3, andt[3] = 4. Is4 < 6? Yes. Move topos = 3, andx = 6 - 4 = 2.
The answer is pos + 1 = 4. Check: prefix(3) = 10 < 12 and prefix(4) = 12 >= 12. The first index with prefix at least 12 is 4. The demo uses a different array, after an update, and prints 3. Both are correct for their arrays.
This descent works only if every value is non-negative. Negative values break the monotone order, and the search can jump past the right answer. Common mistakes lists the real output of that failure.
Counting inversions with coordinate compression
An inversion is a pair of positions i < j where a[i] > a[j]. Counting inversions is the classic use of a Fenwick tree. The problem here is a variant: count pairs where the earlier value is larger, but by no more than D. That is 0 < a[i] - a[j] <= D.
The values can be huge, so the tree cannot be indexed by value directly. Coordinate compression maps each distinct value to its rank among the distinct values. If the values are 5, 1, 4, 2, 3, 4, the sorted distinct values are 1, 2, 3, 4, 5, and each value gets an id from 1 to 5. The tree then has size 5, not 10^9.
The scan goes left to right. Before inserting a[j], count the earlier values that fall in (a[j], a[j] + D]. Those are the earlier positions i with 0 < a[i] - a[j] <= D, which are exactly the pairs we want. Then insert a[j] into the tree.
Worked trace on n = 6, D = 3, and a = 5, 1, 4, 2, 3, 4. The count of earlier values in (a[j], a[j] + 3] is:
j a[j] earlier values in (a[j], a[j]+3] count so far
0 5 (none) (none) 0
1 1 5 (none) 0
2 4 5, 1 5 1
3 2 5, 1, 4 5, 4 3
4 3 5, 1, 4, 2 5, 4 5
5 4 5, 1, 4, 2, 3 5 6The final count is 6. Listing the pairs confirms it: (1,3), (1,4), (1,5), (1,6), (3,4) and (3,5), using 1-based positions. For example (1,4) is a[1] = 5 and a[4] = 2, and 5 - 2 = 3 <= 3.
The C++ code does the same work with upper_bound. above is the number of distinct values that are at most a[j], and upto is the number of distinct values at most a[j] + D. The values in between have ids from above + 1 to upto, so the count is bit.prefix(upto) - bit.prefix(above). The code uses if (upto > above) so that D = 0 gives zero without a negative range.
Real output of the program on that input. The input file has the line 6 3, then 5 1 4 2 3 4:
6The output is the same as the hand trace. The brute force in the same file counts all pairs in O(n^2) and agreed on 3000 random arrays with values from -6 to 6 and sizes up to 15, with D from 0 to 8. Those random arrays have many repeated values, which is where unique and the tie rule matter.
Python version
Python is fine for a Fenwick tree on small inputs, and the code is the same idea. The program below is self-contained, so the site can run it. It builds the tree in O(n), checks the build against repeated add calls, and checks the descent against a loop on 300 random arrays. The random seed is fixed, so the output is the same on every run.
Real output of that program:
prefix(3) = 10 prefix(5) = 15
first index with prefix >= 12: 4
build and descent match brute on 300 random arrays: TruePython is slower than C++ for the same loop. Use the C++ version for the largest inputs. This lesson did not time the Python version, so it makes no claim about its speed.
Hands-on exercise
Do this on your own machine. It takes about 20 minutes.
- Save the C++ file from this lesson as
fen.cpp. Compile it withg++ -O2 -std=c++17 -o fen fen.cpp. - Run
./fen demoand compare the output with the lesson. Your numbers must match exactly. - Run
./fen stress. It should printall stress tests passed. If it prints aFAILline, the message names the test that failed. - Make a file
fen_in1.txtwith the two lines6 3and5 1 4 2 3 4, then run./fen < fen_in1.txt. The output must be6. - Change one value in the sample input to a number you choose, work out the answer by hand with the table from the trace, and check that the program agrees.
- Write a file
fen_big.txtwith200000 50, then 200000 random values from -1000000000 to 1000000000 on the second line. Time./fen < fen_big.txtwithtime. On the lesson machine it took about 0.47 seconds including the input reading. Your time will differ.
Show the answer
Step 5 has no fixed answer. A correct result is one where the hand trace and the program print the same number. Step 6 is a timing exercise. Expect a time well below one second on a normal laptop, and treat any number above a few seconds as a sign that the input reading is slow or the build is not optimised.
Common mistakes
A 0-based index makes the program hang. The loop for (; i <= n; i += i & -i) never moves when i is 0, because 0 & -0 is 0. A test in this lesson called add(0, 5) on a tree of size 4 and the process was still running after the 5 second timeout. The program exited with code 124. The fix is to shift every index by one, so the first element is stored at index 1. Check each caller of add and prefix.
Real output of the pitfall program, a copy of the add loop in the struct above. It prints the first line, and then the 5 second timeout stops the run with exit code 124:
calling add(0, 5)Negative values break the descent. The descent assumes the prefix sums never decrease. A test on a = [3, -2, 4] asked for the first index whose prefix is at least 3. The brute force answered 1, since prefix(1) = 3. Real output of that test:
brute first prefix>=3: 1, descent: 3The fix is to use the descent only on non-negative values, or to use a plain binary search over prefix when values can be negative. The O(log^2 n) version is fine for that case.
Forgetting r + 1 in range updates. The range update needs the second point update at r + 1. Leaving it out makes every later value wrong by v. The point query and range query tests in this lesson catch it at once.
Using int for the sums. A sum of 200000 values near 10^9 needs about 2 * 10^14, which does not fit in a 32-bit int. The code uses long long. In range-update-range-query, the product v * r can be larger than the sum itself, so keep that in long long too.
Compressing without removing duplicates. If vals keeps repeated values, two equal numbers get different ids, so the id ranges no longer match the values and the count can be wrong. unique removes the repeats after sorting. The random tests in this lesson have many repeats, so they would show this kind of error.
Using the wrong bound in compression. For the count of values in (a[j], a[j] + D], the upper end must use upper_bound on a[j] + D, not lower_bound. With lower_bound, a value equal to a[j] + D would be left out.
Checklist
- Indices are 1-based, and no caller passes 0 to
addorprefix. thas sizen + 1, and the O(n) build copies the values in before the loop.- Sums use
long long, and products in range updates are checked for overflow. - Range add with point query updates
landr + 1. - Range add with range query updates four entries, and the second tree stores
d[j] * (j - 1). - Binary descent is used only when every value is non-negative.
- Coordinate compression sorts, removes duplicates, and maps values to ids from 1.
- Every new tree is checked against a brute force on random small inputs with a fixed seed, and the test prints the seed.
Practice problems
These problems use your own machine. Write the code in C++17, test it against a brute force, and check the answer before you open the solution.
Practice 1: Trace the nodes by hand
Take n = 12. List every node i that add(5, v) changes, in the order the loop visits them. Then list every node that prefix(11) reads, in order. Write the blocks each node covers.
Hint: start at i = 5 and apply i += i & -i until you pass 12. For the query, start at 11 and apply i -= i & -i until you reach 0.
Show the answer
add(5, v) changes nodes 5, 6, 8 and 16. Node 16 is outside n = 12, so the loop stops after node 8. The updated nodes are 5, 6 and 8. The blocks are a[5], a[5..6] and a[1..8].
prefix(11) reads nodes 11, 10, 8. Node 8 is a[1..8], node 10 is a[9..10], and node 11 is a[11]. Together they cover 1 to 11.
Practice 2: Count non-inversions
Given an array of n values, count the pairs i < j with a[i] < a[j]. Values can be as large as 10^9, and n is at most 200000.
Hint: the total number of pairs is n * (n - 1) / 2. Subtract the pairs with a[i] > a[j], which you can count with the inversion code, and subtract the pairs with equal values. Count equal pairs from the group sizes after sorting.
Show the answer
The count is n(n - 1)/2 - inversions - equal_pairs, where inversions counts pairs with a[i] > a[j] and equal_pairs counts pairs with a[i] = a[j]. For a value that appears c times, it contributes c(c - 1)/2 equal pairs. The lesson's sample 5 1 4 2 3 4 has 15 pairs, 7 with a[i] > a[j], one equal pair (the two 4s), and 7 increasing pairs. The check is 15 - 7 - 1 = 7. A Python brute force over the same input printed 7 pairs with a[i] > a[j], 1 equal pair and 7 with a[i] < a[j].
Practice 3: k-th smallest with inserts and deletes
Values are integers from 1 to 10^6. You get q operations, up to 200000. Each is + x (insert x), - x (delete one copy of x, guaranteed to exist), or ? k (print the k-th smallest value currently stored, with k at least 1 and at most the current size). Write the solution.
Hint: keep a count for each value in a Fenwick tree over 1..10^6. Insert adds 1 at x, delete adds -1 at x. The k-th smallest is the first index whose prefix count is at least k, which is the descent with all counts non-negative.
Show the answer
Use one Fenwick of size 10^6 holding counts. + x calls add(x, 1), - x calls add(x, -1), and ? k returns first_at_least(k). The counts are never negative, because a delete only happens for a value that exists, so the descent is safe. Test it with a brute force that keeps a sorted vector.
Practice 4: Why one tree is not enough
Explain, with a short example, why range add and range sum needs two Fenwick trees. Write an array of 4 values and two range adds, then show that the range sum over [1, 4] cannot be computed from only the sums of the difference array.
Hint: the sum of a[1..x] counts each change once for each position it reaches. The number of positions depends on where the change starts.
Show the answer
Take a = [0, 0, 0, 0], add 1 to [1, 4], then add 1 to [3, 4]. The array is now 1, 1, 2, 2, and the sum over [1, 4] is 6.
The difference array is d = [1, 0, 1, 0], since the first add changes d[1] and the second changes d[3]. The change at r + 1 = 5 is outside the array.
A tree that stores only d gives b1.prefix(4) = 2. Multiplying by x = 4 gives 8, which is 2 too large. The first change reaches all four positions, but the second reaches only two, so the two changes must be weighted differently. The second tree stores d[j] * (j - 1), which is 0 for j = 1 and 2 for j = 3, so b2.prefix(4) = 2. Then S(4) = 4 * 2 - 2 = 6, which matches the direct sum.
The point of the example is that the second tree records where each change starts. The total of d alone cannot give the answer.
Practice 5: Find the bug
The code below is meant to add v to index i. The caller passes 0-based indices, and the test hangs. Find the bug and fix it.
struct Fenwick {
int n;
vector<long long> t;
Fenwick(int n) : n(n), t(n, 0) {}
void add(int i, long long v) {
for (; i <= n; i += i & -i) t[i] += v;
}
};
// main calls add(i, v) for i = 0 .. n - 1Hint: think about what i & -i returns when i is 0, and about the size of t.
Show the answer
Two bugs. The loop starts at 0, and 0 & -0 is 0, so i never grows and the loop never ends. Also t has size n, not n + 1, so index n is out of bounds. Fix it by making t size n + 1 and calling add(i + 1, v) from the caller, so the first element is index 1.
Summary
A Fenwick tree stores block sums at indices chosen by lowest set bits. That gives O(log n) point changes and prefix queries with a small array. Two trees handle range adds with range sums, binary descent finds the first index that reaches a target when values are non-negative, and coordinate compression lets the tree count values that are large. The checks in this lesson are random tests against brute forces, and the only timing figure is the single run on the lesson machine.