After having a long difficult coding challenge, there was a problem that bugged me. I thought about it for an adequate time but couldn't find the way to solve it. Here, I am providing a problem and example below.

Input

• v : an array of numbers.
• q : 2 dimensional array with 3 elements in nested array.

Description

v is an array and q is a commands that does different thing according to its nested element.

if first element of nested array is 1 => second and third element of the nested array becomes the index and it returns sum[second:third 1] (As you can see, it is inclusive)

if first element of nested array is 2 => element of second index becomes the third. same as v[second] = third

Input example

• v : [1,2,3,4,5]
• q : [[1,2,4], [2,3,8], [1,2,4]]

Example

With a provided example, it goes like

1. command is [1,2,4] => first element is 1. it should return sum from v[2] to v[4] (inclusive) => 12.
2. command is [2,3,8] => first element is 2. it switches v[3] to 8. (now v is [1,2,3,8,5])
3. command is [1,2,4] => first element is 1. it should return sum from v[2] to v[4] (inclusive) => 16, as the third index has been changed from the previous command.

So the final answer is [12, 16]

Question.

The code below is how I solved, however, this is O(n**2) complexity. I wonder how I can reduce the time complexity in this case.

I tried making a hash object, but it didn't work. I can't think of a good way to make a cache in this case.

function solution(v, q) {
  let answer = [];
  for (let i = 0; i < q.length; i  ) {
    let [a, b, c] = q[i];
    if (a === 1) {
      let sum = 0;
      for (let i = b; i <= c; i  ) {
        sum  = v[i];
      }
      answer.push(sum);
    } else if (a === 2) {
      v[b] = c;
    }
  }
  return answer;
}

CodePudding user response：

This type of problem can typically be solved more efficiently with a Fenwick tree

Here is an implementation:

class BinaryIndexedTree extends Array {
    constructor(length) {
        super(length   1);
        this.fill(0);
    }
    add(i, delta) {
        i  ; // make index 1-based
        while (i < this.length) {
            this[i]  = delta;
            i  = i & -i; // add least significant bit
        }
    }
    sumUntil(i) {
        i  ; // make index 1-based
        let sum = 0;
        while (i) {
            sum  = this[i];
            i -= i & -i;
        }
        return sum;
    }
}

function solution(values, queries) {
    const tree = new BinaryIndexedTree(values.length);
    values.forEach((value, i) => tree.add(i, value));
    
    const answer = [];
    for (const [a, b, c] of queries) {
        if (a === 1) {
            answer.push(tree.sumUntil(c) - tree.sumUntil(b - 1));
        } else {
            tree.add(b, c - values[b]);
            values[b] = c;
        }
    }
    
    return answer;
}

let answer = solution([1,2,3,4,5], [[1,2,4], [2,3,8], [1,2,4]]);
console.log(answer);

Time Complexity

The time complexity of running tree.add or tree.sumUntil once is O(log