DSA sheet / Range queries
Dynamic Range Sum Queries
Do these first: Static Range Sum Queries
The problem in brief
You get an array of n integers (up to 200 000) and q operations (up to 200 000). An operation of type 1 sets the value at position k to u; an operation of type 2 asks for the sum of positions a through b (1-indexed, inclusive). Answer every type 2 operation in order.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1648.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
Plain prefix sums answer sums quickly but a single update would force you to rebuild everything. What is the cost of each approach per operation, and why does that fail here?
-
You need a structure where both “change one value” and “sum a prefix” take about O(log n). Think about storing partial sums over blocks whose sizes are powers of two.
-
In a Fenwick tree, position i stores the sum of a block ending at i whose length is the lowest set bit of i. How do you extract that lowest set bit?
-
A point update changes every block containing that position, and a prefix query stitches blocks together. What do the two loops (i += lowbit, i -= lowbit) do? And since an update sets a value while the tree stores sums, what exactly do you add to the tree?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
Compare the two extremes. A raw array gives O(1) update and O(n) query; prefix sums give O(1) query and O(n) update. With 2 * 10^5 mixed operations either extreme costs 4 * 10^10. The fix is a balanced compromise where both are O(log n).
The Fenwick tree (binary indexed tree) does it with an array of size n + 1 where tree[i] holds the sum of the last lowbit(i) elements ending at i, with lowbit(i) = i & -i. To get the prefix sum up to i, add tree[i], then move to i - lowbit(i), and repeat until zero: the blocks you visit tile the prefix exactly. To add a delta at position i, add it to tree[i], then move to i + lowbit(i), and repeat until past n: those are exactly the blocks that contain position i.
Because updates here are assignments, keep the current array and add delta = newValue - oldValue. The habit: decide first whether the data changes; if it does, and you need aggregates, reach for a Fenwick or segment tree, and express every change as an additive delta.
Intuition
Think of tree[i] as a bucket that is responsible for a stretch of the array ending at i, with the stretch length set by the trailing zeros of i. Any prefix is covered by at most log n buckets, and any single element sits in at most log n buckets, so touching them all is cheap.
Approach
- Build the tree by adding every initial value with the update routine (O(n log n)) and keep the values array a[].
- For a type 1 operation (k, u): delta = u - a[k]; a[k] = u; update(k, delta).
- For a type 2 operation (a, b): print query(b) - query(a - 1).
- query(i) sums tree[i], then i -= i & -i, until i = 0. update(i, d) adds d to tree[i], then i += i & -i, until i > n.
Pitfalls: 1-indexed positions (Fenwick trees cannot use index 0); 64-bit sums (up to 2 * 10^14); the delta can be negative; print with one buffered write.
Complexity
O((n + q) log n) time, O(n) memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> tree;
void update(int i, long long d) {
for (; i <= n; i += i & -i) tree[i] += d;
}
long long query(int i) {
long long s = 0;
for (; i > 0; i -= i & -i) s += tree[i];
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
tree.assign(n + 1, 0);
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
update(i, a[i]);
}
string out;
while (q--) {
int type;
cin >> type;
if (type == 1) {
int k;
long long u;
cin >> k >> u;
update(k, u - a[k]);
a[k] = u;
} else {
int l, r;
cin >> l >> r;
out += to_string(query(r) - query(l - 1));
out += '\n';
}
}
cout << out;
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, q = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
tree = [0] * (n + 1)
for i in range(1, n + 1): # O(n) build: push each node's total to its parent block
tree[i] += a[i]
j = i + (i & -i)
if j <= n:
tree[j] += tree[i]
out = []
pos = 2 + n
for _ in range(q):
t = data[pos]
x = int(data[pos + 1])
y = int(data[pos + 2])
pos += 3
if t == '1':
d = y - a[x]
a[x] = y
i = x
while i <= n:
tree[i] += d
i += i & -i
else:
s = 0
i = y
while i > 0:
s += tree[i]
i -= i & -i
i = x - 1
while i > 0:
s -= tree[i]
i -= i & -i
out.append(s)
print("\n".join(map(str, out)))
main()import java.io.*;
public class Main {
static int n;
static long[] tree;
static void update(int i, long d) {
for (; i <= n; i += i & -i) tree[i] += d;
}
static long query(int i) {
long s = 0;
for (; i > 0; i -= i & -i) s += tree[i];
return s;
}
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
st.nextToken();
n = (int) st.nval;
st.nextToken();
int q = (int) st.nval;
tree = new long[n + 1];
long[] a = new long[n + 1];
for (int i = 1; i <= n; i++) {
st.nextToken();
a[i] = (long) st.nval;
update(i, a[i]);
}
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
st.nextToken();
int type = (int) st.nval;
st.nextToken();
int x = (int) st.nval;
st.nextToken();
long y = (long) st.nval;
if (type == 1) {
update(x, y - a[x]);
a[x] = y;
} else {
sb.append(query((int) y) - query(x - 1)).append('\n');
}
}
System.out.print(sb);
}
}const data = require('fs').readFileSync(0, 'utf8').split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
const q = data[1];
const a = new Float64Array(n + 1);
const tree = new Float64Array(n + 1); // sums stay below 2e14, exact in a double
for (let i = 1; i <= n; i++) a[i] = data[1 + i];
function update(i, d) {
for (; i <= n; i += i & -i) tree[i] += d;
}
function query(i) {
let s = 0;
for (; i > 0; i -= i & -i) s += tree[i];
return s;
}
for (let i = 1; i <= n; i++) update(i, a[i]);
const out = [];
let pos = 2 + n;
for (let i = 0; i < q; i++) {
const type = data[pos];
const x = data[pos + 1];
const y = data[pos + 2];
pos += 3;
if (type === 1) {
update(x, y - a[x]);
a[x] = y;
} else {
out.push(query(y) - query(x - 1));
}
}
console.log(out.join('\n'));Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).