Getting TLE while using segment tree in recursive manner

help
1

I am solving a query range sum problem of cses (problem link CSES - Static Range Sum Queries) 1st test case accepted but 2nd got TLE problem(my solution link https://cses.fi/paste/79ef2e432e617e5e27a4d9/) . Is recursive approach is not efficient?? Is i use iterative approach??Please help…

2

Try using the prefix sum.

3

Thanks for your reply, but i want to use segment tree to solve it. I solved it earlier by using prefix sum. I only want to know that what is the efficient way to use segment tree?? is it is recursive or iterative??

4 
ll query(vector<ll>v, ...
...
void built(vector<ll>v,...

Take v by reference instead of value, otherwise, it will be copied on every call to query an built!

5

Thanks, but now it gives run time error instead of TLE. solution link https://cses.fi/paste/87448843a853496e27a647/

6 
segment.resize(2*n);

This should be causing RTE (indirectly). What I mean is, a memory of 2\times N will not be sufficient if you build it that way (where 2 \times i + 1 and 2 \times i + 2 refer to child nodes).

Try with 4\times N. If it still results in RTE, try declaring the variables globally. If still RTE, provide your code sanitized.

7

rr
rr969×471 28.1 KB

Great!! it worked…
Thank you very much for your help.

1 Like
8

Thanks to all of you…
Summary.
1.I pass vector as a copy(which gives me TLE) .
2.I use to store segment tree in vector of 2n(which is wrong, store it in 4n) which gives me RUN TIME ERROR
Thanks once again.

9

Yep: you can easily find a testcase that breaks it with a few seconds of random fuzzing:

[simon@simon-laptop][08:13:05]
[~/tmp/DONTSYNC/hackerrank/otherpeoples]>./compile-latest-cpp.sh 
Compiling shubhamjr-blah.cpp
+ g++ -std=c++14 shubhamjr-blah.cpp -O3 -g3 -Wall -Wextra -Wconversion -DONLINE_JUDGE -D_GLIBCXX_DEBUG -fsanitize=undefined -ftrapv -fno-sanitize-recover
+ set +x
Successful
[simon@simon-laptop][08:13:09]
[~/tmp/DONTSYNC/hackerrank/otherpeoples]>cat last-testcase.txt 
6 1
8 1 8 3 4 8
1 2
[simon@simon-laptop][08:13:13]
[~/tmp/DONTSYNC/hackerrank/otherpeoples]>cat last-testcase.txt | ./a.out 
/usr/include/c++/7/debug/vector:417:
Error: attempt to subscript container with out-of-bounds index 12, but 
container only holds 12 elements.

Objects involved in the operation:
    sequence "this" @ 0x0x5622087535e0 {
      type = std::__debug::vector<long long, std::allocator<long long> >;
    }
Aborted (core dumped)

1.I pass vector as a copy(which gives me RUN TIME ERROR) .

TLE :slight_smile:

1 Like
10

That’s very cool. Thanks.