i_love_emilia_clarke's blog

By i_love_emilia_clarke, history, 6 years ago, In English

Hi, i was wondering how would we carry out these operation on an array using segment tree.

Formal statement of the problem.

Given an array if N positive integers, and Q queries perform these operations.

1 L R X. Decrease every element in the range [L...R] by by value X

2 L R. Return how many element in the range[L...R] are strictly greater than 0

N, Q <= 10^5

0 <= X <= 10000

Initial values of array can be as large as 1 000 000 000 What information would i have to store in each node ?

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

| Write comment?
»
6 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Learn about Lazy propagation.

»
6 years ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

Consider these hints:
1. Segment Tree with each node as a sorted vector of elements in its range.
2. Lazy Propagation on the value to be subtracted.
3. Binary Search on vector for the number of elements > K.

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

    Won't your solution require updates to vectors ? And updating vectors takes O(size of range) time. In the worst case , every update could be O(N).

    Consider a simple case, where the aray is A[1...8].

    First update A[5...8].

    Now, query A[1...8].

    You cannot maintain Lazy array for simple range sum as updates passed on A[5...8] should not affect A[1...4]. Any other way would require updating vector's , isin't it ?

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

      No I am not updating the vectors. For each node, its lazy value will determine the amount, say K that we have to subtract form each number in this node's range. Then querying how many nos are greater than 0 in this range is same as number of elements in the NON-UPDATED vector that are greater than K.

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

        But how shall u maintain the K that we talk about ?

        Consider a simple case, where the array is A[1...8].

        First update A[5...8].

        Now, query A[1...8].

        The lazy for A[1...8] is 0 and u will query its vector for elements greater than 0. However, we have updated elements (5, 6, 7, 8), that initially may have value > 0 , but do not now

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

          For this, we can have two arrays, one is lazy[] and second is changed[]. lazy[node] tells the value that need to be subtracted from elements of that node, while changed[node] is the amount that have been subtracted from each element in that node till now. So we clear the lazy[node] value when we add it to the children's lazy[left/right] and also add it to changed[node]. So while querying a node, we need to see how many numbers are greater than changed[node].

»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I think it is good to split the problem up into three separate standard ones.

The first is to have a tree which can handle range updates, and range query for min value. i.e. Each node must store the min of its range. This requires standard lazy propagation — I'm assuming you know this.

The second is to 'walk' the tree to find the first element which is less than zero, if it exists. How do we do this? We look at the min value. If it is negative, there is a negative element in this range! Else, there isn't. So we can walk to the leaf and erase it if it is negative. Notice that we can do this repeatedly until the overall min is positive. Why? Because the complexity amortizes to O(N log N) as each leaf is only removed once.

Finally, obviously, we must keep track of which nodes are not yet erased by the above. We can use a standard sum tree.

Of course, you may combine everything here. But the reason I explain it separately is to avoid confusion about what is necessary.

Hope this helps.