I've been solving a problem and I found a solution, But I have to maintain some values.
So let's say you have an array and you have 2 types of queries, Which is, Change the value of an element, Add x to all values between l and r, Find the maximum prefix starting from l.
I know how to solve this problem without the range update, But i am stuck with the range update.
Any ideas how to solve this problem ?
Thanks in advance :)
Segment Tree?
how ?
Lazy Propagation?
how?
GFG Lazy Propagation
I know this but what about this problem?How are you going to apply lazy propagation here?
Hey, you are giving me techniques, But not solutions.
What you need is polynomial lazy propagation. As in, at each lazy node, you want a polynomial. For example, you want to add $$$x$$$ to the array from $$$l$$$ to $$$r$$$, then you want to put something like $$$x(i - l)$$$ in the required range in the prefix sum, and $$$x(r-l)$$$ in the later nodes where $$$i$$$ is the variable in your polynomial. Just substitute $$$i$$$ to get the increase of index $$$i$$$. I haven't really carefully considered the indexing so there may be a few off by one errors, but that's the main idea.
Actually i thought of polynomial update in segment tree of prefixes, But i actually don't know how to find the max in range with the polynomial update, I just know how to get the sum.
Any ideas how to get the maximum with the polynomial update ?
Seg tree with lazy. Seg tree supports add value on segment and for each segment in tree contains max prefix sum. For each query divide segment [l, n] into <= log(n) segments of tree and find answer. Complexity to modify log(n), to query — log^2(n).
How would you query in log^2(n) ?
(Assuming by "max prefix" you meant "max prefix sum").
In each node, keep sum and max prefix sum. When updating parent node, max prefix sum is max(max prefix sum of left child, sum of left child + max prefix sum of right child). I believe one can easily add lazy propagation to it.
Now in query, first run a search to decompose [l, r] into O(log n) segments, then do the same: max(max prefix of first segment, sum of first segment + max prefix of second segment, .. and so on). So query time is O(log n) too.
Query time is O(log^2(n)). Because you should to update each segment in the split.
No it isn't. With your logic every segment tree operation is log^2 n lol.
You basically do same thing as standard query, but instead of returning something, you push the id of the node in a list. In total you will visit O(log n) nodes.
Yeah. You are right.
Actually that's the straight forward to think of the problem, But at least for me i am not able to add the lazy propagation to it, Because the maximum prefix will change.
Let's say that the maximum prefix in some segment is 10 and the length is 8 while there is a prefix of length 2 and value of 9, If we did a -2 query for the segment, The best prefix isn't 10 — 2*8, But 9 — 2*2.
So the best prefix isn't fixed, Hope you got the point.
When you add a value $$$x$$$ to a node in the segtree, the position of the maximum prefix sum might change. If you wanted to ‘propagate’ a range update with $$$x$$$ by adding $$$x$$$ to the maximum prefix sum in the node, it would be wrong.
For example, for $$$3, -2, -1$$$ the maximum prefix sum is at position 1 (3), but if you add 3 to the segment, the maximum prefix sum is at position 3 (9). I see little chance that you could actually figure out the new maximum position with your simple 1D segment tree.
To the author: are all values $$$x$$$ positive?
No it doesn't have to.
Using sqrt decomposition and lazy propagation, you can solve this in O(n*sqrt(n)*log(n)). Divide the array into blocks of sqrt(n) and maintain a cht as well as a lazy value for each block. Point update can be done by building the entire block in which the index is present. Range update can be done by adding x to the lazy value of blocks which are completely present inside the range and rebuilding the blocks which are partially inside the range.
For the cht part, you can maintain lines in the form mx + c, where m would be the index and c would be the initial value and x would be the lazy value, which would change after range updates.
I think complexity can be improved to O(n*sqrt(n*log(n))) by adjusting the block size, but didn't give it much thought.
Actually sorry I didn't mention, but you have to solve the queries online not offline.
My approach solves the queries online :)
Lol then i think i didn't understand your approach :)
I think you should be able to use lazy propagation on a dynamic convex hull data structure. (You won't need deletion so that would simplify some things).
The x-coordinates of the points will be prefix sums and the y-coordinates will be the indices. Updates will be to add $$$ay+b$$$ to the x-coordinates of all points with $$$l\leq y\leq r$$$. This can be lazily propagated because it doesn't affect bridge locations if an entire node is updated. Queries are range extreme point queries.
This will be $$$O(\log^2{n})$$$ per query.
If $$$x$$$ is always positive there may be a simpler solution.
Can you elaborate a bit more ? I'm not able to understand how you've removed the requirement of deletion due to the point updates.
Instead of deleting, update the points in place. This is fine because the points are sorted by y-coordinate (index), which does not change. Only the x-coordinate changes.
That's cool thank you very much, but actually in the real problem I don't have to do the range update, but finding dp[i] = max l <= j <= r (dp[j] — (i-j+1)*x) for log n values of x.
Which I found the it can be done in O(log n) using convex hull with li chao tree.
But I really appreciate it thank you very much :)
Can some please link the problem (or another problem with same idea)? It sounds interesting so I want to give it a shot.
maybe make a difference array and create segtree for it, Instead of Range Updates You need Point Updates noww If you didn;t get What I say ..
I can elaborate..