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
T is int, uint, ll, ull, or modint- $0 \leq n \leq 10^8$
Complexity
add
void fw.add(int p, T x)
It processes a[p] += x.
Constraints
Complexity
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
Complexity
Examples
#include <atcoder/fenwicktree>
#include <cstdio>
using namespace std;
using namespace atcoder;
int main() {
int n, q;
scanf("%d %d", &n, &q);
fenwick_tree<long long> fw(n);
for (int i = 0; i < n; i++) {
int a;
scanf("%d", &a);
fw.add(i, a);
}
for (int i = 0; i < q; i++) {
int t;
scanf("%d", &t);
if (t == 0) {
int p, x;
scanf("%d %d", &p, &x);
fw.add(p, x);
} else {
int l, r;
scanf("%d %d", &l, &r);
printf("%lld\n", fw.sum(l, r));
}
}
}