2270. The Total of Each Window Lower Half

n values are given together with a width w. For every window of w consecutive values, print the total of the floor(w / 2) SMALLEST values in that window, counting copies. There are n - w + 1 windows.

When w is 1 the lower half is empty and the total is 0. When w is odd the middle value belongs to neither half and is not counted.

``` n = 6, w = 3, values 1 5 2 8 3 9 floor(3 / 2) = 1

window 1 5 2 sorted 1 2 5 smallest 1 -> 1 window 5 2 8 sorted 2 5 8 smallest 2 -> 2 window 2 8 3 sorted 2 3 8 smallest 2 -> 2 window 8 3 9 sorted 3 8 9 smallest 3 -> 3 ```

## Why a rank cut and not a value cut

The cut is by POSITION IN THE SORTED ORDER, not by value, and the two are different the moment values repeat. Three copies of 5 with w = 3 have a lower half of one value, which is 5, total 5. A cut by value, "everything below the middle value", gives nothing at all and totals 0. Problem 2240 makes the same distinction inside this topic for a collection driven by operations; this is the window form of it.

## What most people try first

Sorting each window, O(n w log w), which at n = w = 2 * 10^5 is past 10^10 before the logarithm.

Two heaps, which is the standard trick for a running median and does work here with care, but a heap cannot remove the value that has just left the window without either a lazy-deletion scheme or a handle per element. Problem 719 is the running median of a window and is worth comparing: the same difficulty appears there and it is the reason this topic exists.

## Why this is a sweep and not an operation list

The earlier problems in this topic are driven by a list of operations: the input says add and del and the structure does as it is told. Here the input is a plain row of values and the removals are implied by POSITION, which is what almost every real use of an ordered set looks like.

step i: insert the value arriving at i remove the value that has just fallen out of the window answer the question about what is left

Those three lines must happen in that order. Doing the removal before the insertion, or answering before both, gives a different answer on every window of width 1, which is why the declared tests include one.

## Two trees of the same shape

Every value is read before the first answer is produced, so every value that can ever be stored is known in advance. Compress them. Then keep two Fenwick trees over the compressed positions, updated by the same insert and remove:

COUNT tree position p holds how many copies of value p the window has SUM tree position p holds value(p) times that count

A descent down the COUNT tree for rank j finds where the jth smallest sits. Accumulating the SUM tree's blocks DURING that same descent gives the total of the first j, so the answer is one walk:

total of the j smallest = sum of every whole block passed on the way down + (values still owed) times (the value landed on)

That second term is the part people drop. The descent stops inside a value that may have several copies, and only some of them are inside the first j, so the remainder is multiplied by the value landed on rather than added once.

## Why a count tree alone is not enough

A count tree can say WHICH value is the jth smallest. It cannot say what the first j add up to, because it never stored the values, only how many of each there are. That is the whole reason for the second tree, and it is the step from pattern 2 of this topic to pattern 3.

## The boundary that breaks a careless implementation

w = 1, where floor(w / 2) is 0 and the total is 0. A descent for rank 0 must return 0 and must not return the smallest value. A declared test has w = 1.

The second is the division: floor(w / 2) on a positive w is the same in every language here, but the rank passed to the descent must be an integer. In JavaScript w / 2 is a floating point number and a descent given 3.5 walks to the wrong place, so truncate it explicitly.

## Overflow

This is where 32 bits stop being enough. A window of 2 * 10^5 values of 10^9 has a lower half of 10^5 values, totalling 10^14, far past the signed 32 bit limit of 2147483647. Negative values reach -10^14 the same way. So the SUM tree and the accumulator are 64 bit, while the COUNT tree holds counts at most w and the VALUES themselves fit in 32 bits. In JavaScript 10^14 is well inside the exact range of a double, which ends at 2^53, about 9 * 10^15, so a plain number is exact and BigInt is not needed.

## Cost

O(n log n) time and O(n) memory.

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ w ≤ n` - `-1000000000 ≤ a[i] ≤ 1000000000` - Values may repeat, and the cut is by rank in the sorted order, not by value. - When `w` is odd the middle value is in neither half. - The intended cost is `O(log n)` per window.