Fenwick Tree
Given an array of length $N$, it processes the following queries in $O(\log N)$ time.
- Updating an element
- Calculating the sum of the elements of an interval
Constructor
fenwick_tree<T> fw(int n)
- It creates an array $a_0, a_1, \cdots, a_{n-1}$ of length $n$. All the elements are initialized to $0$.
Constraints
Tisint,uint,ll,ull, ormodint- $0 \leq n \leq 10^8$
Complexity
- $O(n)$
add
void fw.add(int p, T x)
It processes a[p] += x.
Constraints
- $0 \leq p < n$
Complexity
- $O(\log n)$
sum
T fw.sum(int l, int r)
It returns a[l] + a[l + 1] + ... + a[r - 1].
If T is integer type(int, uint, ll, or ull), it returns the answer in $\bmod 2^{\mathrm{bit}}$, if overflowed.
Constraints
- $0 \leq l \leq r \leq n$
Complexity
- $O(\log n)$
Examples
AC code of https://atcoder.jp/contests/practice2/tasks/practice2_b
import atcoder/header
import atcoder/fenwicktree
let n, q = nextInt()
var fw = init_fenwick_tree[int](n)
for i in 0..<n:
let a = nextInt()
fw.add(i, a)
for i in 0..<q:
let t = nextInt()
if t == 0:
let p, x = nextInt()
fw.add(p, x)
else:
let l, r = nextInt()
echo fw.sum(l..<r)