sajidali6567's blog

CSES: Salary Queries Solution using Dynamic Segment Tree
By sajidali6567, history, 12 months ago, In English

Hi everyone,

I am trying to solve salary queries from CSES using Dynamic Segment Tree. But I am getting TLE.

My understanding of time complexity is: get and update query is log(O(max_value)) which is log(10^9) = 30. There could be 2 * 10^5 queries, and 2 update is done in case of update. so total is 2 * 10^5 * 30 * 2 = 12 * 10^6 and update query is run on input array elements 30 * 2 * 10^5 = 6 * 10^6 so total Complexity is 3 *(6 * 10^6) = 1.8 * 10^7

Problem Link: https://cses.fi/problemset/task/1144 Code Link: https://ideone.com/QfRtXB

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what's the complexity of creating the segtree itself?

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Segment tree is created on demand during query and getSum operations.

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know dynamic segment tree but this problem can be solved with a normal segment tree

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah

    though, you have to do it offline and do some mapping/compression to get it right

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It can be solved online with the solution mentioned in this Blog

      → Reply
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I found the issue. I just did a bit of optimization in algo 1. During getSum we do not need to extend, we can return 0, if it child does not exist (this is where it was failing probably, because it keeps on extending to the leaf) 2. During update I was extending in both the direction everytime (I guess nothing to do with TLE, but important to keep in mind)

        You can check the AC code: https://cses.fi/problemset/result/7797532/

        → Reply
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You are right not_ahmed_hamed, I am referring the same blog primarily. but it uses index compression. Dynamic Segment Tree is another way to solve the problem. You can refer to my implementation for the same.

        → Reply