Блог пользователя faresbasbas

Автор faresbasbas, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится -46 Проголосовать: не нравится

Segment Tree?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    how ?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -52 Проголосовать: не нравится

      Lazy Propagation?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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 ?

»
4 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +6 Проголосовать: не нравится

          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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

        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?

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится
Spoiler
»
4 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

      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.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can some please link the problem (or another problem with same idea)? It sounds interesting so I want to give it a shot.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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