Binary Indexed Tree Test

View as PDF

Submit solution

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

Problem type

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

You have an array of N (1 \le N \le 100\,000) elements, indexed from 1 to N. There are M (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 x-th of the array to v.
  • S l r Output the sum of all the elements from the l-th to the r-th index, inclusive.
  • Q v Output how many elements are less than or equal to v in the array.

At any time, every element in the array is between 1 and 100\,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 N and M.

The second line has N integers, the original array.

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


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


  • 0
    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
      kobortor  commented on Nov. 15, 2015, 10:19 p.m.

      get rid of your exception checking cases.


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


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

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


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

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


      • 1
        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?


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

          Flushing means using

          cout << endl;


          • 0
            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 ;(


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


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

                and the day before fataleagle went to lvl5 ;(


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

                  To be honest Fataleagle is just straight up OP.