Point Update Range Sum
(translated from Chinese using GPT4o) References:
Introduction:
Given an array $$$a$$$, and two integers $$$x, y$$$, perform the following operations:
- Compute the sum of $$$a[x...y]$$$.
- Increment $$$a[x]$$$ by $$$y$$$.
The first operation is called a range sum query, and the second is a point update. While prefix sums suffice for just range sum queries, they fail when updates are involved. For this, we need more advanced data structures to handle both range queries and updates efficiently.
Fenwick Tree (Binary Indexed Tree)
The Fenwick Tree appears first. It may be harder to understand than a segment tree, but its implementation is simpler.
The following diagram illustrates a Fenwick Tree (from OI Wiki):
Properties
Here, $$$a$$$ is the original array, and $$$c$$$ is the Fenwick Tree. The elements of $$$c$$$ store the sums of certain segments of $$$a$$$. But how do we determine which segment $$$a[x...y]$$$ corresponds to $$$c[i]$$$?
First, we observe that $$$y$$$ (the rightmost endpoint of the segment associated with $$$c[i]$$$) is always equal to $$$i$$$. For example, $$$c[4] = \sum a[1...4]$$$. Thus, the key is determining $$$x$$$, the leftmost endpoint.
From the diagram, we observe the following patterns:
- Level 1: Indices $$$1, 3, 5, 7$$$ (all odd numbers).
- Level 2: Indices $$$2, 6$$$.
- Level 3: Index $$$4$$$.
- Level 4: Index $$$8$$$.
Each level represents the range length it covers. For example, at Level 3, $$$c[4]$$$ covers $$$a[1...4]$$$. So, at Level $$$n$$$, $$$c[i]$$$ covers $$$a[i-n+1...i]$$$. Now the problem reduces to determining the level of $$$c[i]$$$.
We introduce binary representation to solve this problem. Let’s summarize:
- Level 1:
- $$$(1)_2 = 1$$$
- $$$(3)_2 = 11$$$
- $$$(5)_2 = 101$$$
- $$$(7)_2 = 111$$$
- All end in $$$1$$$.
- Level 2:
- $$$(2)_2 = 10$$$
- $$$(6)_2 = 1010$$$
- All end in $$$10$$$.
- Level 3:
- $$$(4)_2 = 100$$$
- All end in $$$100$$$.
- Level 4:
- $$$(8)_2 = 1000$$$
- All end in $$$1000$$$.
Thus, the level of $$$c[i]$$$ is determined by the binary representation of $$$i$$$, specifically the lowest set bit and all trailing zeros. This can be computed using lowbit.
Lowbit
lowbit(x) extracts the lowest set bit of $$$x$$$ and all trailing zeros. Using bit manipulation, lowbit(x) = x & -x. Here’s the code:
int lowbit(int x) {
// Extracts the lowest bit and trailing 0s.
return x & -x;
}
Note: lowbit does not return the position of the last set bit but the number represented by $$$1000...$$$ in binary.
Thus, $$$c[x] = \sum_{i=x-\text{lowbit}(x)+1}^x a[i]$$$. This is the sum stored in each Fenwick Tree element.
Query
Given $$$x, y$$$, compute the sum of $$$a[x...y]$$$. For a query like $$$a[1...8]$$$, the answer is simply $$$c[8]$$$. For $$$a[2...8]$$$, the range is split into $$$c[8] - a[1]$$$. Similarly, for $$$a[2...7]$$$, using prefix sums:
$$$a[2...7] = \text{prefix}[7] - \text{prefix}[1]$$$.
Thus, we only need a function to compute $$$a[1...x]$$$ and subtract extra parts, similar to prefix sums.
For $$$a[1...y]$$$, start at i = y and repeatedly jump left (i = i - lowbit(i)) until i = 0.
Code:
int sum(int l, int r) {
int i = r;
int acc = 0;
for (; i > 0; i = i - lowbit(i)) {
acc += f[i];
}
}
Query Time Complexity Proof
(From OI Wiki) Consider the binary representation of $$$r$$$ and $$$l$$$. Their leftmost differing bit (from highest to lowest) determines jumps in the Fenwick Tree. Each jump reduces the problem size logarithmically. Hence, the total complexity is $$$\Theta(\log^2 n)$$$.
Point Update
Point updates reverse the process of range queries. To increment $$$a[x]$$$ by $$$k$$$, update all $$$c[i]$$$ that "cover" $$$a[x]$$$. These are the indices $$$c[x], c[x+\text{lowbit}(x)], c[x+2\times \text{lowbit}(x)], \dots$$$.
Code:
void update(int x, int k) {
for (int i = x; i <= n; i += lowbit(i)) {
c[i] += k;
}
}
Update Time Complexity
During updates, the height of visited nodes strictly increases. For a Fenwick Tree of size $$$n$$$, this height is bounded by $$$\log n$$$. Hence, the complexity is $$$\Theta(\log n)$$$.
Build Tree
Building the tree involves $$$n$$$ point updates, resulting in $$$O(n\log n)$$$ complexity.
Complete Template
template <typename T>
class FenwickTree {
private:
vector<T> c;
int n;
int lowbit(int x) { return x & -x; }
public:
FenwickTree(int size) {
n = size;
c.resize(n + 1, 0);
}
void update(int x, T k) {
for (int i = x; i <= n; i += lowbit(i)) {
c[i] += k;
}
}
T query(int x) {
T sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
sum += c[i];
}
return sum;
}
T rangeQuery(int l, int r) {
return query(r) - query(l - 1);
}
void build(const vector<T>& a) {
for (int i = 1; i <= n; ++i) {
update(i, a[i - 1]);
}
}
};
Example Usage:
int main() {
vector<int> a = {1, 2, 3, 4, 5};
int n = a.size();
FenwickTree<int> fenwick(n);
fenwick.build(a);
cout << "Range [2, 4]: " << fenwick.rangeQuery(2, 4) << endl; // Output: 9
fenwick.update(3, 5);
cout << "After update, range [2, 4]: " << fenwick.rangeQuery(2, 4) << endl; // Output: 14
return 0;
}
Problem Example:
#include <bits/stdc++.h>
using namespace std;
template <typename T>
class FenwickTree {
vector<T> c;
int n;
int lowbit(int x) { return x & -x; }
public:
FenwickTree(int size) {
n = size;
c.resize(n + 1, 0);
}
void update(int x, T k) {
for (int i = x; i <= n; i += lowbit(i)) {
c[i] += k;
}
}
T query(int x) {
T sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
sum += c[i];
}
return sum;
}
T rangeQuery(int l, int r) { return query(r) - query(l - 1); }
void build(const vector<T>& a) {
for (int i = 1; i <= n; ++i) {
update(i, a[i - 1]);
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n);
for (auto& it : a) cin >> it;
FenwickTree<int> ft(n);
ft.build(a);
while (m--) {
int op;
cin >> op;
if (op == 1) {
int x, k;
cin >> x >> k;
ft.update(x, k);
} else {
int l, r;
cin >> l >> r;
cout << ft.rangeQuery(l, r) << endl;
}
}
return 0;
}
Comments (0)
