faresbasbas's blog

By faresbasbas, history, 6 weeks ago, In English

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 :)

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it -46 Vote: I do not like it

Segment Tree?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    how ?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it -52 Vote: I do not like it

      Lazy Propagation?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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 ?

»
6 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

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).

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How would you query in log^2(n) ?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      (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.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Query time is O(log^2(n)). Because you should to update each segment in the split.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it +6 Vote: I do not like it

            Yeah. You are right.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 2   Vote: I like it +6 Vote: I do not like it

        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?

»
6 weeks ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it
Spoiler
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually sorry I didn't mention, but you have to solve the queries online not offline.

»
6 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

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.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      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.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 :)