Getting TLE while using segment tree in recursive manner

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…

Try using the prefix sum.

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

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!

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

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.

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

1 Like

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.

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

1 Like

That’s very cool. Thanks.