Module assignment: warehouse shelf tracker

Why this assignment

This assignment uses everything in the module. You will store one array of shelf values, answer two kinds of range question, and handle changes to single values between the questions. You will start with a version that uses plain loops, then replace each loop with a tree, one at a time. Each step is small and each step can be checked, so you always know whether the change you just made broke anything.

The assignment has no new idea in it. It asks you to put together the point update from lesson 3, the iterative sum and min trees, and the brute-force check from lesson 2. A stretch part at the end asks for a range add, which uses the lazy tag from lesson 4.

The story

A warehouse keeps a long shelf of bins. Bin i holds a number of items, and the number changes all day as staff scan stock in and out. Two questions come in during the day.

The first is the total stock in a run of bins. The second is the smallest count in a run of bins, which tells the manager where the shelf is nearly empty. Both questions are asked about a range of consecutive bins, both ends included. Bins are numbered from 0.

Your job is a program that reads the shelf, reads the day's events in order, and prints the answer to each question.

The specification

Input. The first line holds n, the number of bins. The second line holds n integers, the starting count of each bin. The third line holds m, the number of events. Then come m lines. Each event is one of three forms:

• set i v sets bin i to the count v. Nothing is printed.
• sum l r asks for the total of bins l to r.
• min l r asks for the smallest count among bins l to r.

Output. For each sum or min event, print one line with the answer. Print nothing for set events.

Constraints. 1 <= n <= 800. Each count is from 0 to 1000000. 0 <= l <= r < n in every question. set uses a valid bin number. The judge reads at most 10000 characters of input, so the sizes above fit comfortably. Sums can exceed the int range, so use long long for the total.

Example 1

Input:

6
5 2 8 6 3 7
6
sum 0 5
min 2 3
set 1 9
min 0 5
sum 1 2
set 4 0

Expected output:

31
6
3
17

Check each line by hand. The total of all six bins is 5 + 2 + 8 + 6 + 3 + 7 = 31. The minimum of bins 2 and 3 is min(8, 6) = 6. After set 1 9 the bins are {5, 9, 8, 6, 3, 7}. The minimum of all of them is 3. The total of bins 1 and 2 is 9 + 8 = 17. The last event changes bin 4 but asks nothing, so it prints nothing.

Example 2

Input:

3
4 4 4
4
min 0 2
set 0 1
min 0 2
sum 0 2

Expected output:

4
1
9

The second example shows why the set event matters. The minimum is 4 before the change and 1 after it. A solution that rebuilt only the sum tree and forgot the min tree would print 4 for the third line, and the grader would mark it wrong.

The grading rubric

Your solution is graded on how much of the specification it handles correctly. The three levels below describe what a solution at each level looks like.

60 percent. The program reads the input and answers every sum and min event with a plain loop over the range. Every answer is correct, including after set events, and the program prints nothing for set. The program is simple and has no trees. This is a complete, correct answer for small inputs, and it is the right place to start.

80 percent. Everything in the 60 percent version, plus a sum answered by an iterative sum tree that is updated on every set. The min answers are still loops. The program must keep the tree and the array in step: a set must change the array and the tree together. A common failure at this level is updating the array but not the tree, which gives correct answers for the first few events and wrong ones later.

100 percent. Both sums and minimums are answered by trees, and each set updates both trees. The output matches the samples and the hidden tests. The program handles n = 1, ranges of length 1, ranges that cover the whole array, and events that repeat the same value. The code is clean enough that a teammate could explain each tree in one minute.

Hidden tests check the same three things: correct sums with negative and zero counts, correct minimums after many updates, and single-bin ranges. A solution that passes the samples but fails a hidden test is at the 80 percent level at best.

How to work through the assignment

Work in the order below. Each step produces a program you can run, and each step is safe to keep if the next one fails.

First, read the specification twice and write down the three event forms on a sheet of paper, with one example line for each. Then trace Example 1 by hand, writing the array after each event. Check your traced answers against the expected output before you write any code. Writing the answers down first means you know what the program should print, and a difference is a clue about the code, not a surprise.

Second, write the loop version, Starter A. Run it on both examples. When it passes, save a copy. This copy is your reference for everything that follows, because it is slow but obviously correct.

Third, add the sum tree, Starter B. Keep the loop for the min answers. Test it on both examples. Then write a short test that runs the loop program and the sum-tree program on the same random input. A seeded generator, as in lesson 3, gives a repeatable input. Print any line where the two outputs differ. A difference here is a bug in the sum tree, since the loop is the reference.

Fourth, add the min tree, Starter C, and combine the two trees in one program, which is the reference solution. Run the same random comparison against the loop version, and make sure it still matches after many set events. Pay special attention to the events that change a value and then ask a question about a range that includes it, because those expose a missing update.

Fifth, handle the edges. Try n = 1, a range of one bin, a range covering the whole shelf, and a set that writes the same value the bin already had. Each should give the same answer as the loop.

Sixth, if you want the stretch, add add events last. Keep the old tests running after each change, so you know the stretch did not break the basic part.

A last habit is worth building early. Keep a small file of test inputs that broke an earlier version. Run that file every time you change the code. Bugs that come back are common in tree code, because a fix in one place can break a different path, and the saved tests catch that at once.

Requirements checklist

Work through this list before you submit. Each item is something the grader checks.

• The program reads n, the n counts, m, and then m events in that order.
• set i v changes the stored count of bin i and prints nothing.
• sum l r prints the total of bins l through r, both included.
• min l r prints the smallest count of bins l through r, both included.
• Sums use long long, so totals above 2147483647 print correctly.
• Minimums start from a value larger than any count, such as LLONG_MAX.
• Every set updates the sum structure and the min structure.
• A range of one bin, such as sum 3 3, gives that bin's count.
• A range covering the whole shelf, such as min 0 n-1, gives the global minimum.
• The program works for n = 1.
• Tested against the loop version on at least three different inputs of your own.

Step-by-step hints

Try to finish each step before you open the next hint. Each hint is hidden, so you can check yourself without seeing the answer first.

Starter programs

The three programs below are complete and compile with g++ -std=c++17. Each one is a step toward the full solution. Run each one on Example 1 and check that the output matches the expected output above.

Starter A: the loop version (60 percent)

Type Example 1 into the Input box. The output should be 31, 6, 3 and 17, one per line.

Starter B: the sum tree (80 percent)

Type Example 2 into the Input box. The output should be 4, 1 and 9. The min answer is still a loop here, so this is the version to compare against when you build the min tree.

Starter C: the min tree (80 percent)

Type Example 2 into the Input box. The output should be 4, 1 and 9. Starters B and C together are the 100 percent solution, once you put both trees in one program.

Reference solution

Try the assignment before you open this. The reference uses both trees, updates both on every set, and matches both examples. Run it in the Input box with either example to see the output.

Stretch: range add

The stretch part asks for one more event: add l r v, which adds v to every bin from l to r. This changes many bins at once, so a point update is no longer enough. Use a lazy tag on both trees, as in lesson 4. For a sum node, a tag v adds v times the node's length to the total. For a min node, the same tag adds v to the stored minimum, because adding v to every value shifts the smallest value by exactly v. Write apply and push for both trees, and explain in a short paragraph why the minimum shifts by v and not by v times the length.

Module summary

• A range query asks for a sum, a minimum or a maximum over consecutive positions.
• A plain loop answers in O(n). Prefix sums answer sums in O(1) but cost O(n) per update.
• A segment tree answers both queries and point updates in O(log n), if the operation is associative and has a neutral value.
• A recursive tree uses 4n slots, and the iterative tree uses 2n slots and a simple loop.
• A lazy tag delays a range update, and a push passes it down before the children are read.
• A Fenwick tree handles prefix sums and point updates in about ten lines, but it does not handle minimums.