# Calculating sum after ranged-based subtractions

The puzzle consists from something like this:

You will receive an array of integer with values, then you will receive X numbers. Each number (call it x) represents an index of a 1-indexed array. Look up the value in the array (call it y), then subtract 1 from all the values in the array in the range [x-y, x+y]. The minimum value is 0.

After the given number of operations, you must return the sum of all values in the array.

My code looks like this.

#include <cstdio>
int array;

int main(){
int m,n;
unsigned long long int sum = 0;

//here n is the size of the array, and m is the number of operations
scanf("%d %d", &n, &m);

for (int i = 0; i < n; i++){
scanf("%d", &array[i]);
sum+= array[i];
}

for (int i = 0; i < m; i++) {
int idx;
scanf("%d", &idx);
int count= array[idx - 1];

for (int j = (idx -1 -count >=0 ? idx -1 -count : 0); j < (idx + count <=n ? idx + count : n); j++)
if (array[j]){
sum--;
array[j]--;
}
}

printf("%d\n", sum);
}


It solves the problem, but does not pass in the worst case, that would be a ton of cases decreasing from the entire array, basically an O(n*n) (I think).

The value restrictions are:

• 1 ≤ N,M ≤ 100000;
• Value inside array index between 0 and 50000.

Test case:

Input:

10 4
1 2 0 8 4 2 9 8 1 3
9 5 10 6


Output:

23


Visualization of the test case: For example, the first number that is read is 9. If we treat the number sequence as a 1-indexed array, we read value 1. This means that we need to subtract 1 from every value in the range [9-1, 9+1], which corresponds to the last three elements of the array.

• The problem description makes no sense to me, even with the example. Aug 8, 2016 at 14:00
• Just added an image to help visualizing the test case. Aug 8, 2016 at 14:04
• You say something about a range, while there is only one number? Why if you read a 9 (value 3), you subtract 1 from indeces 7, 8 and 9. What is index 10 of a 0-indexed 10-value array even supposed to mean? Aug 8, 2016 at 14:21
• Sorry for the confusion. The inputs that you receive are based on a 1-indexed array, but my code works with a 0-indexed one, making subtractions to compensate when needed. Aug 8, 2016 at 14:31

### Performance

From what I understand, your solution is as good as it would get. The "n^2" (it's more like O(n*m)) performance seems inevitable. It also seems that an array is the optimal data structure since you must index into it.

If you really want to remove the worst case (decreasing from the entire array), you could keep a count of the number of times you have subtracted from the whole array and let the array value be array[idx] - theCountIMentioned and the final sum be sum - n * theCountIMentioned. Despite this, the performance would still be nearly n^2, especially since decreasing all but one of the values would be an O(n) operation, so the worst case would be O(n * m).

On another note: to make the inner loop more readable consider the following two functions:

inline int min(int a, int b){
return (a < b)? a : b;
}

inline int max(int a, int b){
return (a > b)? a : b;
}


This would make the inner loop's header much more readable. (It would be for(int j = max(0, idx - 1 - count); j < min(idx + count, n); j++)).

Also, you should make the variable names more readable.

• n = arrayLength or even arrLen.
• m = numberOfOps or even opCt.
• Does this solution checks for nodes that are zero (in this case, this node does not subtract from sum). Aug 8, 2016 at 14:22

### Whitespace

Make sure that your whitespace is consistent. The whitespace around operators is very messy, making it more difficult to recognize patterns. Similarly, the usage of whitespace before braces is inconsistent.

### Multi-line for-loop

You have a dangerous multi-line for-loop in your code that has no enclosing braces. Sure... it works. If in a few days time you decide to add something below the if-statement, and just assume that the braces are there "because the if-statement is on multiple lines", you have a difficult time figuring out that the lines below the if-statement are outside the inner for-loop. Instead always use braces, or at least when a multi-line block is used.

### Alternative algorithm

Instead of updating values for each range, you can instead use slightly more memory and save the actual range for each "operation". Now when we need to look up a number, we look at how many ranges intersect that index, and calculate the effective number. The upside of this approach is that instead of updating 100.000 values, we just save 2 values (min and max). The downside is that we need to repeatedly traverse a number of earlier ranges.

You could opt for a hybrid approach, where you save a fixed number of ranges before batch-updating the array.

It would look something like this:

const int buffer = 50;
int min_range[buffer];
int max_range[buffer];

//...

for (int j = 0; ... ) {
scanf("%d", &index);
range = array[index];
for (int k = 0; k < j % buffer; k++) {
if (min_range[k] <= index && index <= max_range[k]) {
range--;
}
}
min_range[k] = index - max(range, 0);
max_range[k] = index + max(range, 0);

if (j % buffer == 0) {
//batch update each index
}
}


For the worst case scenario where we have 100.000 values with 500.000 in them, and 100.000 operations and a buffer of 50, the old situation would require us to write 100.000 * 100.000 values. That's... a lot. Now we only need to write 100.000 * 2 + (100.000 / 50) * 100.000. That's... still a lot, but a lot less. Keep in mind that the larger the buffer, the more intersections have to be calculated. A buffer of 100.000 would mean that the last operation would need to calculate 100.000 intersections before calculating the final range of that operation.

• This solution looks somewhat like the solution that I used, but the complexity of the worst case still greater than 3x10^7, which is the commonly limit that pass on code marathons. Aug 15, 2016 at 14:52

So, after researching and talking to some people, I came up with an answer that runs fast enough to solve the problem in the given time of the puzzle.

The readability still poor on the main, but this code is for coding marathons, readability is not something you should really care when writing code for something like this. But the functions that I got to solve the problem are well written, so I think it will be clear.

The code:

#include <cstdio>

int A;
int tree;
int lazy;

void build(int node, int start, int end)
{
if(start == end)
{
// Leaf node will have a single element
tree[node] = A[start];
}
else
{
int mid = (start + end) / 2;
// Recurse on the left child
build(2*node, start, mid);
// Recurse on the right child
build(2*node+1, mid+1, end);
// Internal node will have the sum of both of its children
tree[node] = tree[2*node] + tree[2*node+1];
}
}

void updateRange(int node, int start, int end, int l, int r, int val)
{
if(lazy[node] != 0)
{
// This node needs to be updated
tree[node] += (end - start + 1) * lazy[node];    // Update it
if(start != end)
{
lazy[node*2] += lazy[node];                  // Mark child as lazy
lazy[node*2+1] += lazy[node];                // Mark child as lazy
}
lazy[node] = 0;                                  // Reset it
}
if(start > end or start > r or end < l)              // Current segment is not within range [l, r]
return;
if(start >= l and end <= r)
{
// Segment is fully within range
tree[node] +=  (end - start + 1) * val;
if(start != end)
{
// Not leaf node;
lazy[node*2] +=val;
lazy[node*2+1] += val;
}
return;
}
int mid = (start + end) / 2;
updateRange(node*2, start, mid, l, r, val);        // Updating left child
updateRange(node*2 + 1, mid + 1, end, l, r, val);   // Updating right child
tree[node] = tree[node*2] + tree[node*2+1];        // Updating root with max value
}

int queryRange(int node, int start, int end, int l, int r)
{
if(start > end or start > r or end < l)
return 0;         // Out of range
if(lazy[node] != 0)
{
// This node needs to be updated
tree[node] += (end - start + 1) * lazy[node];            // Update it
if(start != end)
{
lazy[node*2] += lazy[node];         // Mark child as lazy
lazy[node*2+1] += lazy[node];    // Mark child as lazy
}
lazy[node] = 0;                 // Reset it
}
if(start >= l and end <= r)             // Current segment is totally within range [l, r]
return tree[node];
int mid = (start + end) / 2;
int p1 = queryRange(node*2, start, mid, l, r);         // Query left child
int p2 = queryRange(node*2 + 1, mid + 1, end, l, r); // Query right child
return (p1 + p2);
}

int main(){
int n,m;

scanf("%d %d", &n, &m);

for (int i = 0; i < n; ++i)
scanf("%d", &A[i]);

build(1,0,n-1);

for (int i = 0; i < m; ++i)
{
int idx;
scanf("%d",&idx);

int count = queryRange(1,1,n,idx,idx);

updateRange(1,0,n-1,
(idx -1 -count >=0 ? idx -1 -count : 0),
(idx + count <=n ? idx + count : n)-1,-1);
}

long long sum =0;
for (int i = 1; i <= n; i++) {
int leafval=queryRange(1,1,n,i,i);
sum += leafval > 0 ? leafval : 0;
}

printf("%d\n", sum);
}


The solution is based on a segment tree, more specifically the lazy segment tree implementation.

When I need to update a range, I just update the tree branches that correspond to the range, and mark the children as "dirty".

Every time I need to access a node, I have to check if the node is dirty, and update it when needed.

This way, the update runs at O(log N), so, in the worst case, it will be O(M * log N) for the updates.

After that I need to force update of every leaf of the tree, because I have to check if any leaf got a negative value, and discart them. This costs O(N * log N).

On the end, the code is O((M * log N) + (N * log n)).