Fenwick Tree (Binary Indexed Tree)

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Fenwick {
5
    int n;
6
    vector<long long> bit; // 1-indexed internal array
7
8
    Fenwick(int n_ = 0) { init(n_); }
9
10
    void init(int n_) {
11
        n = max(1, n_);
12
        bit.assign(n + 1, 0LL);
13
    }
14
15
    // O(n) build from 0-based array 'a'
16
    Fenwick(const vector<long long>& a) {
17
        int m = (int)a.size();
18
        n = max(1, m);
19
        bit.assign(n + 1, 0LL);
20
        for (int i = 1; i <= m; ++i) bit[i] = a[i - 1];
21
        // Propagate each node to its parent to form partial sums
22
        for (int i = 1; i <= n; ++i) {
23
            int j = i + (i & -i);
24
            if (j <= n) bit[j] += bit[i];
25
        }
26
    }
27
28
    // Add 'delta' to index 'idx' (1-indexed)
29
    void add(int idx, long long delta) {
30
        for (; idx <= n; idx += idx & -idx) bit[idx] += delta;
31
    }
32
33
    // Prefix sum S(idx) = sum_{i=1..idx} a[i]
34
    long long sumPrefix(int idx) const {
35
        long long res = 0;
36
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
37
        return res;
38
    }
39
40
    // Range sum [l, r] inclusive
41
    long long rangeSum(int l, int r) const {
42
        if (l > r) return 0;
43
        l = max(l, 1);
44
        r = min(r, n);
45
        return sumPrefix(r) - sumPrefix(l - 1);
46
    }
47
};
48
49
int main() {
50
    // Example usage
51
    vector<long long> a = {5, 1, 4, 2, 3}; // indices 1..5
52
    Fenwick ft(a); // O(n) build
53
54
    cout << "Initial prefix sums:\n";
55
    for (int i = 1; i <= (int)a.size(); ++i) {
56
        cout << "S(" << i << ") = " << ft.sumPrefix(i) << '\n';
57
    }
58
59
    cout << "\nRange sum [2, 4] = " << ft.rangeSum(2, 4) << '\n'; // 1+4+2 = 7
60
61
    // Point update: a[3] += 6 (indexing is 1-based in the tree)
62
    ft.add(3, 6);
63
    cout << "After adding 6 at position 3, range [2, 4] = " << ft.rangeSum(2, 4) << '\n'; // 1+(4+6)+2 = 13
64
65
    return 0;
66
}
67

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Fenwick {
5
    int n; vector<long long> bit;
6
    Fenwick(int n_ = 0) { init(n_); }
7
    void init(int n_) { n = max(1, n_); bit.assign(n + 1, 0LL); }
8
    void add(int idx, long long delta) { for (; idx <= n; idx += idx & -idx) bit[idx] += delta; }
9
    long long sumPrefix(int idx) const { long long s = 0; for (; idx > 0; idx -= idx & -idx) s += bit[idx]; return s; }
10
};
11
12
// Supports: add v to range [l, r], and query value at a single point x
13
struct FenwickRangeUpdatePointQuery {
14
    Fenwick ft; // stores the difference array d
15
    FenwickRangeUpdatePointQuery(int n = 0) : ft(n) {}
16
    void init(int n) { ft.init(n); }
17
18
    // add v to all a[i] for i in [l, r]
19
    void addRange(int l, int r, long long v) {
20
        if (l > r) return;
21
        ft.add(l, v);
22
        if (r + 1 <= ft.n) ft.add(r + 1, -v);
23
    }
24
25
    // value at a single point x
26
    long long pointQuery(int x) const {
27
        return ft.sumPrefix(x);
28
    }
29
};
30
31
int main() {
32
    int n = 8;
33
    FenwickRangeUpdatePointQuery ds(n);
34
35
    // Start with all zeros. Perform some range increments.
36
    ds.addRange(2, 5, 3);   // a[2..5] += 3
37
    ds.addRange(4, 8, -2);  // a[4..8] -= 2
38
    ds.addRange(1, 1, 10);  // a[1] += 10
39
40
    cout << "Point values after range updates:\n";
41
    for (int i = 1; i <= n; ++i) {
42
        cout << "a[" << i << "] = " << ds.pointQuery(i) << '\n';
43
    }
44
45
    return 0;
46
}
47

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Fenwick {
5
    int n; vector<long long> bit;
6
    Fenwick(int n_ = 0) { init(n_); }
7
    void init(int n_) { n = max(1, n_); bit.assign(n + 1, 0LL); }
8
    void add(int idx, long long delta) { for (; idx <= n; idx += idx & -idx) bit[idx] += delta; }
9
    long long sumPrefix(int idx) const { long long s = 0; for (; idx > 0; idx -= idx & -idx) s += bit[idx]; return s; }
10
};
11
12
// Maintain array a[1..n] with: add v to [l, r], query sum over [l, r]
13
struct FenwickRangeUpdateRangeQuery {
14
    Fenwick B1, B2; // Two BITs implementing the classic trick
15
    FenwickRangeUpdateRangeQuery(int n = 0) : B1(n), B2(n) {}
16
    void init(int n) { B1.init(n); B2.init(n); }
17
18
    // Internal helper to apply add at index idx on both trees
19
    void _internalAdd(int idx, long long mul, long long add) {
20
        B1.add(idx, mul);
21
        B2.add(idx, add);
22
    }
23
24
    // Add v to all a[i], i in [l, r]
25
    void addRange(int l, int r, long long v) {
26
        if (l > r) return;
27
        _internalAdd(l,  v, v * (l - 1));
28
        if (r + 1 <= B1.n) _internalAdd(r + 1, -v, -v * r);
29
    }
30
31
    // Prefix sum up to x after all range adds
32
    long long prefix(int x) const {
33
        long long s1 = B1.sumPrefix(x);
34
        long long s2 = B2.sumPrefix(x);
35
        return x * s1 - s2;
36
    }
37
38
    // Range sum [l, r]
39
    long long rangeSum(int l, int r) const {
40
        if (l > r) return 0;
41
        return prefix(r) - prefix(l - 1);
42
    }
43
};
44
45
int main() {
46
    int n = 10;
47
    FenwickRangeUpdateRangeQuery ds(n);
48
49
    // Add ranges
50
    ds.addRange(2, 7, 5);   // a[2..7] += 5
51
    ds.addRange(4, 10, 3);  // a[4..10] += 3
52
53
    cout << "Sum [1, 3] = " << ds.rangeSum(1, 3) << '\n';  // expected: only [2,3] got +5 => 10
54
    cout << "Sum [4, 7] = " << ds.rangeSum(4, 7) << '\n';  // expected: (5+3)*4 = 32
55
    cout << "Sum [8, 10] = " << ds.rangeSum(8, 10) << '\n'; // expected: 3*3 = 9
56
57
    return 0;
58
}
59

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Fenwick {
5
    int n; vector<long long> bit;
6
    Fenwick(int n_ = 0) { init(n_); }
7
    void init(int n_) { n = max(1, n_); bit.assign(n + 1, 0LL); }
8
    void add(int idx, long long delta) { for (; idx <= n; idx += idx & -idx) bit[idx] += delta; }
9
    long long sumPrefix(int idx) const { long long s = 0; for (; idx > 0; idx -= idx & -idx) s += bit[idx]; return s; }
10
11
    // Find smallest idx such that sumPrefix(idx) >= k. Requires all frequencies >= 0 and total sum >= k.
12
    int kth(long long k) const {
13
        int idx = 0;
14
        // Largest power of two >= n
15
        int bitMask = 1;
16
        while (bitMask << 1 <= n) bitMask <<= 1;
17
        for (int step = bitMask; step > 0; step >>= 1) {
18
            int next = idx + step;
19
            if (next <= n && bit[next] < k) {
20
                k -= bit[next];
21
                idx = next;
22
            }
23
        }
24
        return idx + 1; // 1-based index
25
    }
26
};
27
28
int main() {
29
    // Suppose we maintain frequencies of values 1..10
30
    Fenwick freq(10);
31
32
    // Insert some values: frequencies at positions
33
    vector<int> vals = {1, 2, 2, 3, 5, 5, 5, 9};
34
    for (int v : vals) freq.add(v, 1);
35
36
    // Total count is 8. Let's find the median (k = 4) and also k = 6.
37
    int k1 = 4, k2 = 6;
38
    int idx1 = freq.kth(k1);
39
    int idx2 = freq.kth(k2);
40
41
    cout << "k=4 -> value " << idx1 << '\n'; // expected 3 (1,2,2,3,...)
42
    cout << "k=6 -> value " << idx2 << '\n'; // expected 5
43
44
    // Remove one '5' and find k=6 again
45
    freq.add(5, -1);
46
    cout << "After removing a 5, k=6 -> value " << freq.kth(6) << '\n';
47
48
    return 0;
49
}
50