troubleshooting Question

O(log n) queries for subsequence problem

Avatar of Dastas
Dastas asked on
16 Comments1 Solution474 ViewsLast Modified:

I have to solve the following problem in O(log n) for both updates and queries... the problem statement goes like this:

Given n numbers, answer m questions like this: what is the value of the highest sum subsequence in the interval [A, B], 1<= A <= B <= n?

My idea is to use an interval / segment tree, but I'm not sure how to build, query and update it...

I'd appreciate any pointers. I don't want any other code except maybe pseudo-code, I'm only after some ideas about how to solve this efficiently...
Join the community to see this answer!
Join our exclusive community to see this answer & millions of others.
Unlock 1 Answer and 16 Comments.
Join the Community
Learn from the best

Network and collaborate with thousands of CTOs, CISOs, and IT Pros rooting for you and your success.

Andrew Hancock - VMware vExpert
See if this solution works for you by signing up for a 7 day free trial.
Unlock 1 Answer and 16 Comments.
Try for 7 days

”The time we save is the biggest benefit of E-E to our team. What could take multiple guys 2 hours or more each to find is accessed in around 15 minutes on Experts Exchange.

-Mike Kapnisakis, Warner Bros