Explanation:

A straight forward implementation would start with an array for and perform modifications, where the elements for are getting the value added.

This would need

operations, so it is . The constraints require to handle up to and resulting in about operations, which is outside the given resources.

The above solution manages to requires setup steps and a final integration step visiting not more than array elements, so it is . For the constraints not more than about steps are needed, which is possible to compute with the given resources.

In Detail:

Let us start with the continuous case:

We start with a constant function and then add the modifications, going through a sequence of modified functions .

Given and adding the value for all times , this results into the modified function

where is the characteristic function of set and is the Heaviside distribution The derivative is where is the Dirac distribution.

For the discrete case this seems to turn into

with

So the modeling of the derivative is very efficient, only recording the changes at the interval borders.

After modifications of the constant null function we get:

Finally is reconstructed by summing up (integrating) over :

where we used as smallest value.