*A writeup of Dec number 3 from the USACO platinum problem set*

### Counting Haybales

##### Problem Statement

FJ’s farm consists of N fields in a row, conveniently numbered 1…N. In each field there can be any number of haybales. Farmer John’s instructions contain three types of entries:

1) Given a contiguous interval of fields, add a new haybale to each field. 2) Given a contiguous interval of fields, determine the minimum number of haybales in a field within that interval. 3) Given a contiguous interval of fields, count the total number of haybales inside that interval.

From these three requirements, we know the problem probably requires implementing a data structure. Specifically, such a data structure must support **O(log N)** range updates, range sums, and range minimum queries.

##### Lazy RMQ

In order to support range operations, we need to augment the traditional segment tree.

The rationale behind our solution is that we want to postpone updates as much as possible. Due to the nature of a segment tree, we can often apply updates to an entire range at a time. We only need to resolve these updates when we’re actually querying inside the range.

For example, consider the node with value **9**. It spans the range 0 to 2. If we wanted to make a range update from say, 0 to 3, we would only need to update nodes **9** and **7**. Node **9** covers (0, 2) and node **7** covers (3, 3) (these values are inclusive).

In pseudocode, our update function is

Update range(left, right, delta):

- If our current interval is completely inside
(left, right), change our node’s pending update counter bydelta- If our current node has pending updates, apply it, and pass on these updates downwards to its child nodes.
- If our current interval is overlaps with but is not inside
(left, right), recursively call update on the child nodes. Then recalculate our current node’s value.

A Java implementation is as follows

```
/**
* @param idx Index
* @param il Left bound of interval at idx
* @param ir Right bound of interval at idx
* @param delta Amount to update each element in (ul, ur) by
* @param ul Left bound of update interval
* @param ur Right bound of update interval
*/
void update(int idx, int il, int ir, int delta, int ul, int ur) {
// If completely contained, change current update counter
if (ul <= il && ir <= ur) {
updates[idx] += delta;
}
processLazy(idx);
if (il > ur || ir < ul || (ul <= il && ir <= ur)) {
return;
}
// Recursively called upon child nodes
int mid = (il + ir) / 2;
update(l(idx), il, mid, delta, ul, ur);
update(r(idx), mid + 1, ir, delta, ul, ur);
// Recalculate current node
recalc(idx);
}
void processLazy(int idx) {
if (updates[idx] != 0) {
// Apply pending update
tree[idx] += updates[idx];
// Pass pending update downwards to child nodes
if (valid(l(idx))) updates[l(idx)] += updates[idx];
if (valid(r(idx))) updates[r(idx)] += updates[idx];
// Reset the update amount
updates[idx] = 0;
}
}
```

##### Range Sums

Similarly, this technique can be applied to a Segment Tree for range sums. That implementation is left as an exercise to the reader.

My solution can be found here

*Written by Robert Chen*

Notice any mistakes? Please email us at [email protected] so that we can fix any inaccuracies.