Calculating sum after ranged-based subtractions
Performance
From what I understand, your solution is as good as it would get. The &quot;n^2&quot; (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).
Readability
On another note: to make the inner loop more readable consider the following two functions:
inline int min(int a, int b){
    return (a &lt; b)? a : b;
}

inline int max(int a, int b){
    return (a &gt; 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 &lt; min(idx + count, n); j++)).
Also, you should make the variable names more readable.

n = arrayLength or even arrLen.
m = numberOfOps or even opCt.