Prefix, sparse and Fenwick

Questions 1 to 5 of 8

1. 1. Take a = [5, 1, 4, 2, 3] and a prefix array pre with pre[0] = 0 and pre[i] = a[0] + ... + a[i - 1]. What is pre[4] - pre[1], the sum over the half-open range [1, 4)?

   Type a number.

2. 2. An AI wrote a difference array for "add v to every index from l to r, both included". It does d[l] += v and d[r] -= v. The array has 5 cells, all zero, and the call is add(1, 3, 3). What does the final array look like?

   Indices 0 to 4 hold 0, 3, 3, 0, 0. Index 3 misses the +3, because the stop point for an inclusive range is r + 1.Indices 0 to 4 hold 0, 3, 3, 3, 0. The code is correct because d[r] -= v stops the change at r.Indices 0 to 4 hold 0, 3, 3, 3, 3. The -3 at index 3 is ignored because it is past the middle of the array.Indices 0 to 4 hold 0, 0, 0, 0, 0. The changes cancel, because +3 and -3 are both applied to the same range.
3. 3. A plain sparse table answers each range query with two blocks that can overlap. Which of these range operations are correct with that plain overlapping table?

   Pick every answer that is true.

   Range sumRange minimumRange XORRange gcd
4. 4. For s = [1, 2, 3, 4, 5, 6, 7], the range [0, 6) has the true sum 21. A plain sparse table uses the overlapping blocks [0, 4) and [2, 6), which add to 28. How much of that 28 comes from the overlap [2, 4) being counted twice?

   Type a number.

5. 5. Put the Fenwick nodes that prefix(7) reads, in the order the loop for (; i > 0; i -= i & -i) visits them.

   Use the arrows to put the steps in order.

   1. 1.t[6], which covers a[5..6]↑↓
   2. 2.t[7], which covers a[7]↑↓
   3. 3.t[4], which covers a[1..4]↑↓