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 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 element 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
    31501357  commented on March 18, 2022, 11:05 p.m.

    Someone should have told me that the largest element in the array is at most 100000, would have saved a lot of time implementing an order statistic tree.


    • 9
      BalintR  commented on March 19, 2022, 1:53 a.m.

      It says in the problem statement.

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


  • 2
    ross_cleary  commented on March 29, 2020, 8: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.


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

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


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

        Makes sense, thank you.


  • 2
    faraz123  commented on March 29, 2020, 6: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?


  • 4
    Cueball1234  commented on Feb. 17, 2018, 5:51 p.m. ← edit 2

    TLE

    I know my solution is \mathcal{O}(M \log 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. 16, 2015, 3:15 a.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, 5:37 a.m.

      It also happen to me


    • 1
      kobortor  commented on Nov. 16, 2015, 3:19 a.m.

      get rid of your exception checking cases.


      • 2
        minecraftyugi  commented on Nov. 16, 2015, 3:33 a.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, 5:13 a.m.

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


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

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


      • 1
        pyrexshorts  commented on March 8, 2015, 4:50 p.m.

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