[問題案]Point Add Range Sum(point_add_range_sum)

yosupo06 / library-checker-problems

The problem data (Test case generator, judge's solution, task, ...) of Library Checker

https://judge.yosupo.jp/

Apache License 2.0

521 stars 118 forks source link

[問題案]Point Add Range Sum(point_add_range_sum) #20

Closed yosupo06 closed 5 years ago

yosupo06 commented 5 years ago

長さNの数列a_iにQ個のクエリ

1 k x: a_k += x
2 l r: sum al ~ a{r-1}

N, Q <= 500,000(200,000?) 0 <= a_i, x <= 1e9

想定

fenwick tree
segment tree

Maruoka842 commented 4 years ago

代入の＝は一般的でなくて混乱するので、\leftarrow （$a_p=a_p+x$ の＝）の方がよいと思います。

jpfr12 commented 4 years ago

Hi everyone. if segment tree is a possible solution, can anyone tell me what's wrong with my implementation? it gives TLE on "max_sum" tests ;( my code: https://judge.yosupo.jp/submission/15281