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
what's the complexity of creating the segtree itself?
Segment tree is created on demand during query and getSum operations.
I don't know dynamic segment tree but this problem can be solved with a normal segment tree
yeah
though, you have to do it offline and do some mapping/compression to get it right
It can be solved online with the solution mentioned in this Blog
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/
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.
bro submitting ur soln gives tle still