Submit Info #3028

Problem Lang User Status Time Memory
Point Add Range Sum pypy3 knuu AC 847 ms 129.71 MiB

ケース詳細
Name Status Time Memory
example_00 AC 39 ms 25.79 MiB
max_random_00 AC 840 ms 128.58 MiB
max_random_01 AC 847 ms 129.71 MiB
max_random_02 AC 844 ms 127.87 MiB
max_random_03 AC 842 ms 127.85 MiB
max_random_04 AC 840 ms 127.80 MiB
random_00 AC 683 ms 108.83 MiB
random_01 AC 719 ms 118.20 MiB
random_02 AC 458 ms 57.99 MiB
random_03 AC 279 ms 99.72 MiB
random_04 AC 298 ms 86.50 MiB
small_00 AC 51 ms 29.10 MiB
small_01 AC 49 ms 29.15 MiB
small_02 AC 47 ms 29.10 MiB
small_03 AC 49 ms 29.13 MiB
small_04 AC 49 ms 29.10 MiB
small_05 AC 49 ms 29.19 MiB
small_06 AC 50 ms 29.22 MiB
small_07 AC 49 ms 29.14 MiB
small_08 AC 51 ms 29.22 MiB
small_09 AC 52 ms 29.22 MiB

import sys input = sys.stdin.readline class FenwickTree: """FenwickTree (Binary Indexed Tree, 0-index) Queries: 1. add(i, val): add val to i-th value 2. sum(n): sum(bit[0] + ... + bit[n-1]) complexity: O(log n) See: http://hos.ac/slides/20140319_bit.pdf """ def __init__(self, a_list): self.N = len(a_list) self.bit = a_list[:] for _ in range(self.N, 1 << (self.N - 1).bit_length()): self.bit.append(0) for i in range(self.N-1): self.bit[i | (i+1)] += self.bit[i] def add(self, i, val): while i < self.N: self.bit[i] += val i |= i + 1 def sum(self, n): ret = 0 while n >= 0: ret += self.bit[n] n = (n & (n + 1)) - 1 return ret def query(self, low, high): return self.sum(high) - self.sum(low) def yosupo(): # https://judge.yosupo.jp/problem/point_add_range_sum _, Q = map(int, input().split()) fwt = FenwickTree([int(x) for x in input().split()]) ans = [] for _ in range(Q): type_, l, r = map(int, input().split()) if type_ == 0: fwt.add(l, r) else: ans.append(fwt.query(l-1, r-1)) print(*ans, sep="\n") def aoj(): # https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B N, Q = map(int, input().split()) fwt = FenwickTree([0] * N) ans = [] for _ in range(Q): type_, l, r = map(int, input().split()) if type_ == 0: fwt.add(l-1, r) else: ans.append(fwt.query(l-2, r-1)) print(*ans, sep="\n") if __name__ == "__main__": yosupo() # aoj()