acl_cpp.fenwicktree

• C++ version documentation

• Source code

fenwicktree.fenwick_tree

# fenwick_tree<ll>
from acl_cpp.fenwicktree import fenwick_tree

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

• Updating an element

• Calculating the sum of the elements of an interval

Constructor

# fenwick_tree::fenwick_tree(int n)
def fenwick_tree(n: int = 0) -> fenwick_tree

Creates an array \(a_0, a_1, \dots, a_{n-1}\) of length \(n\). All elements are initialized to \(0\).

Constraints

• \(0 \leq n < 2^{31}\)

Complexity

• \(O(n)\)

add

# void fenwick_tree::add(int p, ll x)
def fenwick_tree.add(p: int, x: int) -> None

Performs a[p] += x.

Constraints

• \(0 \leq p < n\)

Complexity

• \(O(\log n)\)

sum

# ll fenwick_tree::sum(int l, int r)
def fenwick_tree.sum(l: int, r: int) -> int

Returns a[l] + a[l + 1] + ... + a[r - 1]. If the answer does not fit in a 64-bit signed integer, returns the value equal to the answer mod \(2^{64}\).

Constraints

• \(0 \leq l \leq r \leq n\)

Complexity

• \(O(\log n)\)

Examples

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

from acl_cpp.fenwicktree import fenwick_tree

N, Q = map(int, input().split())
a = list(map(int, input().split()))

fw = fenwick_tree(N)
for i in range(N):
    fw.add(i, a[i])

for _ in range(Q):
    t, a, b = map(int, input().split())
    if t == 0:
        fw.add(a, b)
    else:
        print(fw.sum(a, b))