🗂️Data StructureIntermediate

Fenwick Tree - Range Update Range Query

Key Points

  • •
    A Fenwick Tree (Binary Indexed Tree) can support range additions and range sum queries by maintaining two trees, often called B1 and B2.
  • •
    Think in terms of a difference array d: adding v to [l, r] means increases by v and decreases by v.
  • •
    Store d in B1 and store (i−1)· in B2; then prefix sum up to x is x·sum(B1, x) − sum(B2, x).
  • •
    Range sum over [l, r] equals prefix(r) − prefix(l−1) using the combined query from both BITs.
  • •
    Each update or query runs in O(log n) time, and the structure uses O(n) space.
  • •
    Use 1-indexing internally for Fenwick operations; convert from 0-indexed inputs carefully.
  • •
    Long long (64-bit) is recommended to avoid overflow when multiplying indices and values.
  • •
    This approach is simpler and faster than a full segment tree with lazy propagation for pure range-add/range-sum tasks.

Prerequisites

  • →Prefix Sums — Fenwick Trees generalize prefix sums with efficient updates; understanding prefix-to-range conversion is essential.
  • →Difference Arrays — Range additions become two point updates on the difference array, the foundation of the two-BIT trick.
  • →Bit Manipulation (lowbit) — Fenwick traversal uses the least significant set bit (x & −x) to navigate.
  • →1-indexed vs 0-indexed Arrays — Fenwick implementations are typically 1-indexed; careful conversions prevent off-by-one errors.
  • →Integer Overflow and 64-bit Arithmetic — Indices multiply values in queries; using long long prevents overflow on large inputs.
  • →Segment Tree Basics (optional contrast) — Helps understand when two-BIT is preferable or when a segment tree with lazy propagation is needed.

Detailed Explanation

Tap terms for definitions

01Overview

A Fenwick Tree (also called a Binary Indexed Tree, or BIT) is a compact data structure for maintaining prefix sums with logarithmic-time updates and queries. By default, a single Fenwick Tree supports point updates and prefix sum queries. However, many problems require applying the same increment to an entire range and then asking for the sum of elements over a range. With a neat trick, we can extend the Fenwick Tree to support Range Update and Range Query (RURQ) in O(log n) per operation by maintaining two Fenwick Trees simultaneously. The core idea is to view the array through its difference array d, where each range increment translates into only two point updates in d. Then, because we want sums of the original array, we track both d and a weighted version of d so that we can reconstruct any prefix sum using a simple formula. This method is elegant, memory-efficient, and very fast in practice, making it popular in competitive programming and systems that need high-throughput cumulative operations.

02Intuition & Analogies

Imagine a long row of cups labeled 1 through n. The value a_i is how much water sits in cup i. If we pour v units of water into every cup from l to r, doing it cup-by-cup is slow. Instead, consider tracking changes at the boundaries: place a sign at l that says "+v starts here" and another at r+1 that says "−v stops here". When you walk from cup 1 to cup x, you tally the sum of all signs you've passed; that tells you how much has been added to each cup up to x. This 'signs' method is exactly the difference array d. Now, if someone asks for the total water in cups 1..x, it's not enough to know how much each individual cup gained; you need the combined total. Here's a second insight: if the +v effect started far back, it contributes to many cups; if it started recently, it affects fewer. That means older starts are 'heavier' for the prefix sum. We capture this by keeping another tally that weights each boundary sign by where it appears. With two ledgers—one for raw starts/stops and one for their weighted positions—you can compute the total water efficiently for any prefix. A Fenwick Tree is the perfect tool because it supports quick updates to these ledgers and quick queries of their cumulative totals.

03Formal Definition

Let a be a 1-indexed array, and define the difference array d by and − for , with . A range increment of v on [l, r] translates to ← + v and ← − v (if r+1 ≤ n). The array can be recovered by = . We wish to answer range sum queries S(l, r) = quickly while also performing range increments. Define D(x) = and ID(x) = i·. Then the prefix sum of a up to x is P(x) = = (x+1)·D(x) − ID(x). To compute P(x) efficiently, maintain two Fenwick Trees: B1 storing (so B1.query(x) = D(x)) and B2 storing (i−1)· (so B2.query(x) = (i−1)·) − D(x)). Consequently, P(x) = x·B1.query(x) − B2.query(x). Range sum over [l, r] follows as S(l, r) = P(r) − P(l−1). Range add [l, r] with v is performed by point updates on both trees: B1.add(l, v), B1.add(r+1, −v); B2.add(l, v·(l−1)), B2.add(r+1, −v·r).

04When to Use

Use a two-BIT (Fenwick) approach when you need to support two operations efficiently: adding a constant to every element of a subarray [l, r], and querying the sum of elements over a subarray [l, r]. This shows up in problems involving repeated range increments, difference constraints, frequency range updates, prefix-sum-based scoring, and cumulative counters where updates are bulk but queries are diverse. It is especially effective in competitive programming where O(log n) per operation at scale (n, q up to 2e5 or more) is required. If you only need point updates and range sums, a single Fenwick is sufficient. If you need more complex operations (like range minimum, max, or affine updates), consider a segment tree with lazy propagation. However, for pure range add and range sum, the two-BIT solution is simpler, often faster due to low constants, easier to implement correctly under time pressure, and uses O(n) space. It’s also a good fit when memory is constrained but performance demands are high.

⚠️Common Mistakes

  1. Off-by-one indexing: Fenwick trees are naturally 1-indexed. If your inputs are 0-indexed, you must convert l and r to 1-based before updates and queries. 2) Forgetting the r+1 update: Range add [l, r] requires B1.add(l, v) and B1.add(r+1, −v) (similarly for B2). Skipping the r+1 update breaks the 'stop' boundary and yields incorrect tails. 3) Miscomputing B2 updates: For range add v to [l, r], you must add v·(l−1) at l and −v·r at r+1. Using v·l or v·(r+1) is wrong and will shift sums. 4) Overflow: Since prefix computations multiply by indices (up to n), use 64-bit integers (long long) for both trees and intermediate products, especially if values or n can be large. 5) Querying the wrong function: The prefix value of a_x is D(x), but the prefix sum P(x) requires the combined formula x·B1.query(x) − B2.query(x). Don’t return D(x) when asked for range sums. 6) Not guarding r+1 bounds: Only apply updates at r+1 if r < n. Allocate arrays of size at least n+2 to simplify edge handling. 7) Mixing inclusive/exclusive ranges: Fenwick-based range updates assume inclusive [l, r]. Be consistent across problem I/O and internal methods. 8) Building from an initial array incorrectly: To build from a, convert to differences d and update B1 with d_i and B2 with (i−1)·d_i; or simulate rangeAdd(i, i, a_i).

Key Formulas

Difference Array Definition

Explanation: This defines the difference array d for a. It encodes how values change between consecutive indices, making range additions become two point updates.

Recover a from d

Explanation: The original array value at position x equals the sum of differences up to x. Walking across differences accumulates all started increments.

Prefix Sum via Differences

Explanation: Here D(x) = and ID(x) = i . This identity reconstructs the sum of the first x elements using d and its index-weighted sum.

Range Sum from Prefix Sums

Explanation: Any inclusive range sum can be obtained as the difference of two prefix sums. This is the standard conversion from prefix to range queries.

Range Add as Two Point Updates

Explanation: Adding v to every in [l, r] only changes the boundaries in d: it starts at l and stops at r+1. If , the r+1 update is omitted.

Two-BIT Prefix Formula

Explanation: If B1 stores D(x) and B2 stores (i-1) , then the prefix sum of a up to x is x·B1.query(x) − B2.query(x). This matches the implementation-friendly formula.

Lowbit Operation

Explanation: The least significant set bit determines Fenwick jumps. Adding it moves upward to parent; subtracting it moves downward to accumulate sums.

Time and Space Complexity

Explanation: Each add or query touches at most one node per bit in the index, giving logarithmic time. The tree arrays store O(n) values.

Equivalent Prefix Identities

Explanation: Both forms are mathematically identical. Storing (i−1)· as the second BIT makes the computational form x·D(x) − (ID(x) − D(x)) convenient.

Range Sum via Two-BIT Prefix

Explanation: Apply the prefix formula at r and l−1 and subtract. This is exactly what rangeSum(l, r) does in code.

Complexity Analysis

Let n be the array size and q the number of operations. A Fenwick Tree maintains partial sums aligned to powers of two; an update or query climbs or descends the implicit tree by repeatedly adding or subtracting the least significant set bit, which takes at most O(log n) steps because each step clears one binary digit. In the two-BIT approach for range update and range query, every logical operation makes a constant number of Fenwick operations: rangeAdd([l, r], v) performs up to four point updates (two on B1 and two on B2), each O(log n), for a total of O(log n). A prefixSum(x) performs two Fenwick prefix queries (one on B1 and one on B2) and a couple of O(1) arithmetic operations; thus it is O(log n). A rangeSum(l, r) calls prefixSum twice, still O(log n). Building from scratch in the naive way by applying n single-index rangeAdd(i, i, ) costs O(n log n). If you convert the initial array to differences d and insert them directly into B1 and B2 with O(log n) point updates per i, it is also O(n log n). Memory usage is O(n) for each BIT; with two trees the total is O(n). The hidden constant factors are very small (tight loops, few memory touches), making Fenwick Trees faster than many alternatives like segment trees for this specific operation mix. Overall, total runtime for q operations is O(q log n) and space is O(n).

Code Examples

Two-BIT Fenwick: Range Add and Range Sum (Core Implementation)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Fenwick {
5    int n;
6    vector<long long> bit; // 1-indexed Fenwick tree
7    Fenwick() : n(0) {}
8    explicit Fenwick(int n_) { init(n_); }
9    void init(int n_) {
10        n = n_;
11        bit.assign(n + 1, 0LL);
12    }
13    // Add value v at index i (1-indexed)
14    void add(int i, long long v) {
15        for (; i <= n; i += i & -i) bit[i] += v;
16    }
17    // Prefix sum query sum_{1..i}
18    long long sum(int i) const {
19        long long res = 0;
20        for (; i > 0; i -= i & -i) res += bit[i];
21        return res;
22    }
23};
24
25struct FenwickRange {
26    int n;
27    Fenwick B1, B2; // B1 stores d_i, B2 stores (i-1)*d_i
28    FenwickRange() : n(0) {}
29    explicit FenwickRange(int n_) { init(n_); }
30    void init(int n_) {
31        n = n_;
32        B1.init(n);
33        B2.init(n);
34    }
35    // Internal helper: add v to difference at position i on B1 and (i-1)*v on B2
36    void _diff_add(int i, long long v) {
37        if (i <= 0) return; // guard if someone passes 0
38        if (i > n) return;  // ignore r+1 if it is n+1 and trees sized n
39        B1.add(i, v);
40        B2.add(i, v * (i - 1));
41    }
42    // Range add: add v to a[l..r], with 1 <= l <= r <= n
43    void range_add(int l, int r, long long v) {
44        _diff_add(l, v);
45        if (r + 1 <= n) _diff_add(r + 1, -v);
46    }
47    // Prefix sum of a up to x: P(x) = x*sum(B1,x) - sum(B2,x)
48    long long prefix_sum(int x) const {
49        if (x <= 0) return 0LL;
50        if (x > n) x = n;
51        long long s1 = B1.sum(x);
52        long long s2 = B2.sum(x);
53        return s1 * x - s2;
54    }
55    // Range sum over [l, r]
56    long long range_sum(int l, int r) const {
57        if (l > r) return 0LL;
58        l = max(l, 1);
59        r = min(r, n);
60        return prefix_sum(r) - prefix_sum(l - 1);
61    }
62};
63
64int main() {
65    ios::sync_with_stdio(false);
66    cin.tie(nullptr);
67
68    int n = 10;
69    FenwickRange fw(n);
70
71    // Add 5 to [3, 7]
72    fw.range_add(3, 7, 5);
73    // Add -2 to [6, 10]
74    fw.range_add(6, 10, -2);
75
76    // Query some ranges
77    cout << fw.range_sum(1, 10) << "\n"; // total sum
78    cout << fw.range_sum(3, 3) << "\n";  // a[3]
79    cout << fw.range_sum(7, 9) << "\n";  // sum over [7..9]
80
81    return 0;
82}
83

This code builds a two-BIT structure to support range additions and range sum queries. B1 holds d_i and B2 holds (i−1)·d_i. Range updates are translated into boundary updates on both trees, and queries use P(x) = x·sum(B1, x) − sum(B2, x).

Time: O(log n) per add or querySpace: O(n)
Building from an Initial Array and Verifying with a Naive Checker
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Fenwick {
5    int n; vector<long long> bit;
6    Fenwick() : n(0) {}
7    explicit Fenwick(int n_) { init(n_); }
8    void init(int n_) { n = n_; bit.assign(n + 1, 0); }
9    void add(int i, long long v){ for(; i <= n; i += i & -i) bit[i] += v; }
10    long long sum(int i) const { long long r=0; for(; i>0; i -= i & -i) r += bit[i]; return r; }
11};
12
13struct FenwickRange {
14    int n; Fenwick B1,B2;
15    FenwickRange(): n(0) {}
16    explicit FenwickRange(int n_) { init(n_); }
17    void init(int n_) { n=n_; B1.init(n); B2.init(n); }
18    void _diff_add(int i, long long v){ if(i<=0||i>n) return; B1.add(i,v); B2.add(i, v*(i-1)); }
19    void range_add(int l,int r,long long v){ _diff_add(l,v); if(r+1<=n) _diff_add(r+1,-v); }
20    long long prefix_sum(int x) const { if(x<=0) return 0; if(x>n) x=n; long long s1=B1.sum(x), s2=B2.sum(x); return s1*x - s2; }
21    long long range_sum(int l,int r) const { if(l>r) return 0; l=max(l,1); r=min(r,n); return prefix_sum(r)-prefix_sum(l-1); }
22    // Build from initial array a[1..n]
23    void build_from_array(const vector<long long>& a){
24        // Build differences and load into B1, B2
25        for(int i=1;i<=n;i++){
26            long long di = a[i] - (i>1 ? a[i-1] : 0LL);
27            _diff_add(i, di);
28        }
29    }
30};
31
32int main(){
33    ios::sync_with_stdio(false);
34    cin.tie(nullptr);
35
36    int n = 8;
37    vector<long long> a(n+1); // 1-indexed
38    // initial array
39    a[1]=3; a[2]=1; a[3]=4; a[4]=1; a[5]=5; a[6]=9; a[7]=2; a[8]=6;
40
41    FenwickRange fw(n);
42    fw.build_from_array(a);
43
44    // Perform some range updates
45    fw.range_add(2, 5, 10);
46    fw.range_add(4, 8, -3);
47
48    // Naive checker
49    vector<long long> naive = a;
50    for(int i=2;i<=5;i++) naive[i]+=10;
51    for(int i=4;i<=8;i++) naive[i]+=-3;
52
53    // Compare multiple queries
54    for(int l=1;l<=n;l++){
55        for(int r=l;r<=n;r++){
56            long long fast = fw.range_sum(l,r);
57            long long slow = 0; for(int i=l;i<=r;i++) slow += naive[i];
58            if(fast != slow){
59                cerr << "Mismatch at ["<<l<<","<<r<<"] fast="<<fast<<" slow="<<slow<<"\n";
60                return 0;
61            }
62        }
63    }
64    cout << "All checks passed!\n";
65    return 0;
66}
67

Shows how to initialize the two BITs from an existing array by computing differences d_i and inserting them. It also validates correctness against a naive array updated element-wise.

Time: Build O(n log n), each update/query O(log n)Space: O(n)
Competitive Programming I/O: Q operations for Range Add and Range Sum
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Fenwick{
5    int n; vector<long long> bit;
6    void init(int n_){ n=n_; bit.assign(n+1,0); }
7    void add(int i,long long v){ for(; i<=n; i+=i&-i) bit[i]+=v; }
8    long long sum(int i) const { long long r=0; for(; i>0; i-=i&-i) r+=bit[i]; return r; }
9};
10
11struct FenwickRange{
12    int n; Fenwick B1,B2;
13    void init(int n_){ n=n_; B1.init(n); B2.init(n); }
14    void _diff_add(int i,long long v){ if(i<=0||i>n) return; B1.add(i,v); B2.add(i, v*(i-1)); }
15    void range_add(int l,int r,long long v){ _diff_add(l,v); if(r+1<=n) _diff_add(r+1,-v); }
16    long long prefix_sum(int x) const { if(x<=0) return 0; if(x>n) x=n; long long s1=B1.sum(x), s2=B2.sum(x); return s1*x - s2; }
17    long long range_sum(int l,int r) const { if(l>r) return 0; l=max(l,1); r=min(r,n); return prefix_sum(r)-prefix_sum(l-1); }
18};
19
20int main(){
21    ios::sync_with_stdio(false);
22    cin.tie(nullptr);
23
24    int n, q; cin >> n >> q;
25    FenwickRange fw; fw.init(n);
26
27    // Optional: read initial array and build
28    vector<long long> a(n+1,0);
29    for(int i=1;i<=n;i++){ cin >> a[i]; }
30    // Build by differences
31    for(int i=1;i<=n;i++){
32        long long di = a[i] - (i>1? a[i-1]:0LL);
33        fw._diff_add(i, di);
34    }
35
36    // Process queries
37    // Type 1 l r v  => add v to [l, r]
38    // Type 2 l r    => print sum of [l, r]
39    for(int qi=0; qi<q; ++qi){
40        int type; cin >> type;
41        if(type==1){
42            int l, r; long long v; cin >> l >> r >> v;
43            fw.range_add(l, r, v);
44        } else if(type==2){
45            int l, r; cin >> l >> r;
46            cout << fw.range_sum(l, r) << '\n';
47        }
48    }
49    return 0;
50}
51

This is a typical CF-style solution skeleton: build from an initial array using differences, then handle two types of operations—range add and range sum—each in O(log n). It uses long long to avoid overflow.

Time: O((n + q) log n)Space: O(n)