Fenwick Tree Range

Fenwick tree supporting both range add and range sum queries using two BITs.

[Data Structures]|

Jul 9, 2026

|explanatory_notes.md|

#fenwick#bit#range-add#range-sum

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 2e5 + 5;
ll mul[MAXN], add[MAXN];
int n;

void bitAdd(int i, ll m, ll c) {
    for (; i <= n; i += i & -i) {
        mul[i] += m;
        add[i] += c;
    }
}

void rangeAdd(int l, int r, ll v) {
    bitAdd(l, v, -v * (l - 1));
    bitAdd(r + 1, -v, v * r);
}

ll prefSum(int i) {
    ll s = 0;
    int pos = i;
    for (; i > 0; i -= i & -i)
        s += pos * mul[i] + add[i];
    return s;
}

ll query(int l, int r) {
    return prefSum(r) - prefSum(l - 1);
}

31 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Fenwick Tree with Range Updates

Supports range add and range sum simultaneously using two BITs, built on the difference array concept.

Key Identity

If $d[i] = a[i] - a[i-1]$ is the difference array, then:

\sum_{i=1}^{k} a[i] = k \sum_{i=1}^{k} d[i] - \sum_{i=1}^{k} (i-1) \cdot d[i]

Two BIT arrays (mul and add) maintain these two components.

Operations

rangeAdd(l, r, v) — add

v

to all elements in

[l, r]

query(l, r) — sum of elements in

[l, r]

When to Use

Range add + range sum (lazy BIT)

Simpler than lazy segment tree when only addition is needed

Complexity

Update / Query —

O(\log n)

Space —

O(n)