Given an array a of n integers, and q queries, for each value from index l to index r, add x to the value

userA4Hl1 0
Viewed 40

I have an array, and for each query, I need to add x to all the values from index l to index r. For example, if I had the array 1 0 1 0 1, and three queries of the form l, r, x: 1 2 1 3 5 3 1 5 2 I'd have to add 1 to values in the array from index 1 to index 2, then 3 from index 3 to index 5, then 2 from index 1 to index 5. The final array would be 4 3 6 5 6. How would this be done efficiently? I tried simply iterating over the values from l to r, but that did not work.

arrays algorithm
3 Answers
userh4sx0

The naive method is to follow the instructions of shifting l, r, x into possession then iterating from l to r adding x

var arr = [1, 0, 1, 0, 1]
var q = [1, 2, 1, 3, 5, 3, 1, 5, 2];

while (q.length) {
  var l = q.shift();
  var r = q.shift();
  var x = q.shift()

  for (var i = l - 1; i < r; i++) {
    arr[i] += x;
  }
}

console.log("" + arr)

IT goldman0

With the problems of this kind, observe that each query l, r, x is in fact two queries: l, end, x and r+1, end -x.

Once you split them in in the pairs, sort them by the start index (O(q log q)), and obtain the result in a single O(n) pass.

user586970
Related