Binary Indexed Tree Test

View as PDF

Submit solution

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 NN (1 \le N \le 100\,000)(1 \le N \le 100\,000) elements, indexed from 11 to NN. There are MM (1 \le M \le 500\,000)(1 \le M \le 500\,000) operations you need to perform on it.

Each operation is one of the following:

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

At any time, every element in the array is between 11 and 100\,000100\,000 (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 NN and MM.

The second line has NN integers, the original array.

The next MM 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

Comments


  • 2
    ross_cleary  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.


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

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


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

        Makes sense, thank you.


  • 3
    faraz123  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?


  • 3
    Cueball1234  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.


  • 1
    minecraftyugi  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.


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

      It also happen to me


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

      get rid of your exception checking cases.


      • 2
        minecraftyugi  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...


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

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


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

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


      • 2
        pyrexshorts  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?


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

          Flushing means using

          cout << endl;


          • 2
            bobhob314  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 ;(


            • 2
              kobortor  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.


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

                and the day before fataleagle went to lvl5 ;(


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

                  To be honest Fataleagle is just straight up OP.