## Binary Indexed Tree Test

View as PDF

Points: 10 (partial)
Time limit: 1.4s
Memory limit: 256M

Problem type

Xyene is doing a contest. He comes across the following problem:

You have an array of elements, indexed from to . There are operations you need to perform on it.

Each operation is one of the following:

• C x v Change the -th element of the array to .
• S l r Output the sum of all the elements from the -th to the -th index, inclusive.
• Q v Output how many elements are less than or equal to in the array.

At any time, every element in the array is between and (inclusive).

Xyene knows that one fast solution uses a Binary Indexed Tree. He practices that data structure every day, but still somehow manages to get it wrong. Will you show him a working example?

#### Input Specification

The first line has and .

The second line has integers, the original array.

The next lines each contain an operation in the format described above.

#### Output Specification

For each S or Q operation, output the answer on its own line. Note that you may need to use 64-bit integers to store the answer.

#### Sample Input

10 10
4 8 4 5 6 3 2 2 8 1
C 7 6
Q 7
S 2 3
S 1 4
C 4 9
S 2 3
Q 6
C 3 9
S 6 7
Q 6

#### Sample Output

8
12
21
12
7
9
6

• commented on March 29, 2020, 4:01 p.m.

Can someone take a look at my code, I am wrong answering on the first three cases and I don't know what the problem is.

• commented on March 29, 2020, 4:11 p.m.

Change while(value <= N) to while(value <= maxvalue).

• commented on March 29, 2020, 4:34 p.m.

Makes sense, thank you.

• commented on March 29, 2020, 2:39 p.m. edited

At any time, every element in the array is between 1 and 100000 (inclusive).

Is this talking about the test cases themselves or something that needs to be factored in the solution?

• commented on Feb. 17, 2018, 12:51 p.m. edited

TLE

I know my solution is O(Mlog(N)), but it still seems I am TLEing. Could someone please tell me why this is happening? Thank you!

Edit: Turns out upper_bound and lower_bound are slow.

• commented on Nov. 15, 2015, 10:15 p.m.

I'm just wondering, is my algorithm for solving the question wrong? I'm TLEing on 3 test cases, but I can't seem to figure out what's causing the problem.

• commented on Sept. 1, 2021, 1:37 a.m.

It also happen to me

• commented on Nov. 15, 2015, 10:19 p.m.

get rid of your exception checking cases.

• commented on Nov. 15, 2015, 10:33 p.m. edited

I changed the exceptions to if and else statements, but it didn't change much.

EDIT: calculating values beforehand is always a good idea...

• commented on March 8, 2015, 12:13 a.m.

I submit the exact same code, but only one TLE's on cases...

• commented on March 8, 2015, 12:18 a.m.

Flushing output is not guaranteed to be a constant time on every judge.

• commented on March 8, 2015, 12:50 p.m.

I'm not sure what you mean? Does that mean my code is technically correct time-wise or?

• commented on March 8, 2015, 12:53 p.m.

Flushing means using

cout << endl;

• commented on March 8, 2015, 1:58 p.m.

kobortor u snake going to level 3 on the same day i went to lvl 2 ;(

• commented on March 8, 2015, 9:36 p.m.

And the same day you went to lvl 2 awaykened and jefferyxiao went to lvl 4.

• commented on March 9, 2015, 6:40 p.m.

and the day before fataleagle went to lvl5 ;(

• commented on March 9, 2015, 6:44 p.m.

To be honest Fataleagle is just straight up OP.