USACO NOV08 Problem 'lites' Analysis

by Long Fan

In short, our problem is that we should maintain a huge 01 array a, which supports these two operations:
  • 1.Switch all values in a given range of array.
  • 2.Output the sum of all values in a given range of array a.
  • In this problem, the size of the array could be 100,000, so we need an algorithm which takes O(log N) for each of these two operations. The official solution uses a data structure called segtree, which basically is storing things in segments of length 2^i.

    	         |____________|
    	        1              6
            |_________|         |_________|
           1           3       4           6
        |______|    |___|    |______|    |___|
       1       2    3   3    4      5    6   6
     |__|   |___|          |___|  |___|         
    1    1  2   2         4    4  5   5
    

    The above graph shows a simple segtree example built on the array with size 6. We start our building process with a node to represent the entire array. Each time a we need to modify a segment with length more than 1, we break it into two small segments and set these two as the children of this big segment. An important fact about segtrees is that for any given [l, r], we can use at most 2*log_n nodes in seg tree to cover it. For example, for the segmennt [3, 5], we can use two nodes, [3, 3] and [4, 5] to cover it.

    We need to output the sum of a given range in this problem. In order to exploit the segtree construction, we store for each node in segtree, the sum of the elements in the interval represented by this node. For example, node [4, 6] will store the sum of a[4]+a[5]+a[6]. Then, for each query about sum of an interval, we can just find the at most 2*log_n segments to cover this interval and output their sum. This can be done in O(log n) time.

    However, trouble comes when we try to switch the value of an segment. When switching the value in a seg tree node, the straightforward method is to switch the sum in that node along with the sums of all its children. However, some query might switch the value of the entire array and cause O(n) operations.

    The solution to this problem is lazy propagation. That is, when we encounter a switch operation for a node in seg tree, we do not immediately do the switch operation on this node and all its children. We just create a sign on this node to represent that this node has been switched and postpone the real switch operation until this node is queried by output sum operation. What's left is the situation where a node involved in the summation has the sign. We first resolve this sign, then set the signs of its two children (propagation) and fix the sum of this node to the switched value.

    With lazy propagation, we simply find a set of nodes in the seg tree which cover this given interval and look at all its signs. We do not actually need to perform the switch during update, but rather postpone it to the sum query. This lowers the complexity of the switch operation to O(log n) and leaves the complexity of the sum operation unchanged.