Segment tree or Fenwick?

2000ms

262144K

Description:

This is an unusual problem in an unusual contest, here is the announcement: http://codeforces.com/blog/entry/73543

You are given an array $$$A$$$ of length $$$n$$$, initially filled with zeros. You need to process $$$q$$$ queries to the array, each of one of the following types:

1 x y: you need to assign $$$A_x=y$$$;
2 l r: you need to print $$$\sum\limits_{i=l}^r A_i$$$.

Furthermore, there are $$$T$$$ independent tests you need to process.

Input:

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$) — the number of test cases.

Each test case description starts with two integers $$$n, q$$$ ($$$1 \leq n, q \leq 10^5$$$) — the length of the array and the number of queries. The following $$$q$$$ lines contain the description of queries: $$$1~x~y$$$ ($$$1 \leq x \leq n$$$, $$$0 \leq y \leq 10^9$$$) for queries of the first type and $$$2~l~r$$$ ($$$1 \leq l \leq r \leq n$$$) for queries of the second type.

It is guaranteed that the sum of $$$n$$$ as well as the sum of $$$q$$$ does not exceed $$$10^6$$$.

Output:

For each query of the second type print its result on a separate line.

Sample Input:

Sample Output:

Informação

Provedor Codeforces

Código CF1302C