Fenwick Tree

Given an array of length $N$, it processes the following queries in $O(\log N)$ time.

Constructor

fenwick_tree<T> fw(int n)

Constraints

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

AC code of https://atcoder.jp/contests/practice2/tasks/practice2_b

#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)); } } }