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

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.

CodePudding user response：

For mutable range queries you should opt for Segment Tree

Building a segment tree will take O(n) time. (One time process)

Each query takes O(log n) time

Using this, you can achieve the results with efficiency.

Take a look here: https://cp-algorithms.com/data_structures/segment_tree.html

CodePudding user response：

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)