Task · data processing hard JavaScript ·

Range add, range sum

/**
 * @param {number[]} nums
 * @param {Array[]} ops
 * @returns {number[]}
 */
function range_add_sum(nums, ops)

range_add_sum([1, 2, 3, 4], [["sum", 0, 3], ["add", 1, 2, 10], ["sum", 0, 1], ["sum", 2, 3]])  // -> [10, 13, 17]
range_add_sum([5], [["add", 0, 0, -5], ["sum", 0, 0]])  // -> [0]

• #1Google Gemini 3.8 Flashsolved · 10 of 10 testsanswer in 5.2 s · runtime 544 ms · $0.0032

  ✓	range_add_sum([1, 2, 3, 4], [["sum", 0, 3], ["add", 1, 2, 10], ["sum", 0, 1], ["sum", 2, 3]])expected [10, 13, 17]	3 ms
  ✓	range_add_sum([5], [["add", 0, 0, -5], ["sum", 0, 0]])expected [0]	1 ms

  ✓ 2 ms✓ <1 ms✓ 25 ms✓ 2 ms✓ 2 ms✓ 1 ms⏱ 360 ms⏱ 147 ms
  Code

  /**
   * @param {number[]} nums
   * @param {Array[]} ops
   * @returns {number[]}
   */
  function range_add_sum(nums, ops) {
    const n = nums.length;
    if (n === 0) return [];
  
    // Binary Indexed Tree (Fenwick tree) with range updates and range queries
    // Maintains: A[i] = nums[i] initially, plus updates.
    // sum(0..i) = (sum(B1, i) * (i + 1)) - sum(B2, i)
    // To add v to [l, r]:
    // add(B1, l, v), add(B1, r + 1, -v)
    // add(B2, l, v * l), add(B2, r + 1, -v * (r + 1))
  
    const b1 = new Float64Array(n + 2);
    const b2 = new Float64Array(n + 2);
  
    function bitAdd(idx, v) {
      const vIdx = v * idx;
      for (let i = idx + 1; i <= n; i += i & -i) {
        b1[i] += v;
        b2[i] += vIdx;
      }
    }
  
    function rangeAdd(l, r, v) {
      bitAdd(l, v);
      // For r + 1:
      const idx2 = r + 1;
      const v2 = -v;
      const vIdx2 = v2 * idx2;
      for (let i = idx2 + 1; i <= n; i += i & -i) {
        b1[i] += v2;
        b2[i] += vIdx2;
      }
    }
  
    function prefixSum(idx) {
      if (idx < 0) return 0;
      let s1 = 0;
      let s2 = 0;
      for (let i = idx + 1; i > 0; i -= i & -i) {
        s1 += b1[i];
        s2 += b2[i];
      }
      return s1 * (idx + 1) - s2;
    }
  
    // Precompute initial prefix sums of nums to avoid N updates
    const pref = new Float64Array(n + 1);
    for (let i = 0; i < n; i++) {
      pref[i + 1] = pref[i] + nums[i];
    }
  
    const results = [];
    const len = ops.length;
    for (let i = 0; i < len; i++) {
      const op = ops[i];
      if (op[0] === 'add') {
        rangeAdd(op[1], op[2], op[3]);
      } else {
        const l = op[1];
        const r = op[2];
        const initialSum = pref[r + 1] - pref[l];
        const addedSum = prefixSum(r) - prefixSum(l - 1);
        results.push(initialSum + addedSum);
      }
    }
  
    return results;
  }

• #2DeepSeek V4.1 Flashsolved · 10 of 10 testsanswer in 1.5 s · runtime 1.3 s · $0.0005

  ✓	range_add_sum([1, 2, 3, 4], [["sum", 0, 3], ["add", 1, 2, 10], ["sum", 0, 1], ["sum", 2, 3]])expected [10, 13, 17]	2 ms
  ✓	range_add_sum([5], [["add", 0, 0, -5], ["sum", 0, 0]])expected [0]	1 ms

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ 2 ms⏱ 727 ms⏱ 578 ms
  Code

  function range_add_sum(nums, ops) {
    const n = nums.length;
    const size = 1 << Math.ceil(Math.log2(n || 1));
    const sum = new Float64Array(2 * size);
    const lazy = new Float64Array(2 * size);
  
    for (let i = 0; i < n; i++) sum[size + i] = nums[i];
    for (let i = size - 1; i > 0; i--) sum[i] = sum[2 * i] + sum[2 * i + 1];
  
    function apply(node, l, r, v) {
      sum[node] += v * (r - l + 1);
      lazy[node] += v;
    }
  
    function push(node, l, r) {
      const v = lazy[node];
      if (v !== 0) {
        const mid = (l + r) >> 1;
        apply(2 * node, l, mid, v);
        apply(2 * node + 1, mid + 1, r, v);
        lazy[node] = 0;
      }
    }
  
    function update(node, l, r, ql, qr, v) {
      if (ql > r || qr < l) return;
      if (ql <= l && r <= qr) {
        apply(node, l, r, v);
        return;
      }
      push(node, l, r);
      const mid = (l + r) >> 1;
      update(2 * node, l, mid, ql, qr, v);
      update(2 * node + 1, mid + 1, r, ql, qr, v);
      sum[node] = sum[2 * node] + sum[2 * node + 1];
    }
  
    function query(node, l, r, ql, qr) {
      if (ql > r || qr < l) return 0;
      if (ql <= l && r <= qr) return sum[node];
      push(node, l, r);
      const mid = (l + r) >> 1;
      return query(2 * node, l, mid, ql, qr) + query(2 * node + 1, mid + 1, r, ql, qr);
    }
  
    const res = [];
    for (let i = 0; i < ops.length; i++) {
      const op = ops[i];
      if (op[0] === "add") {
        update(1, 0, size - 1, op[1], op[2], op[3]);
      } else {
        res.push(query(1, 0, size - 1, op[1], op[2]));
      }
    }
    return res;
  }

• #3OpenAI GPT-6 Lunanot solved · 4 of 10 testsanswer in 4.1 s · runtime 1.9 s · $0.0003

  ✓	range_add_sum([1, 2, 3, 4], [["sum", 0, 3], ["add", 1, 2, 10], ["sum", 0, 1], ["sum", 2, 3]])expected [10, 13, 17]	3 ms
  ✗	range_add_sum([5], [["add", 0, 0, -5], ["sum", 0, 0]])expected [0]returned [-5]	<1 ms

  ✓ <1 ms✓ 3 ms✗ wrong answer✓ 1 ms✗ wrong answer✗ wrong answer⏱ wrong answer⏱ wrong answer
  Code

  function range_add_sum(nums, ops) {
    const n = nums.length;
    const size = Math.ceil(Math.sqrt(n));
    const blocks = Math.ceil(n / size);
    const sums = new Float64Array(blocks);
    const lazy = new Float64Array(blocks);
  
    for (let i = 0; i < n; i++) sums[Math.floor(i / size)] += nums[i];
  
    function prefix(end) {
      let total = 0;
      let i = 0;
      while (i <= end) {
        const b = Math.floor(i / size);
        const blockEnd = Math.min(n - 1, (b + 1) * size - 1);
        if (i === b * size && blockEnd <= end) {
          total += sums[b] + lazy[b] * (blockEnd - i + 1);
          i = blockEnd + 1;
        } else {
          total += nums[i] + lazy[b];
          i++;
        }
      }
      return total;
    }
  
    const result = [];
    for (const op of ops) {
      const l = op[1], r = op[2];
      if (op[0] === "sum") {
        result.push(prefix(r) - (l ? prefix(l - 1) : 0));
        continue;
      }
  
      const v = op[3];
      let i = l;
      while (i <= r) {
        const b = Math.floor(i / size);
        const blockEnd = Math.min(n - 1, (b + 1) * size - 1);
        if (i === b * size && blockEnd <= r) {
          sums[b] += v * (blockEnd - i + 1);
          lazy[b] += v;
          i = blockEnd + 1;
        } else {
          nums[i] += v;
          sums[b] += v;
          i++;
        }
      }
    }
    return result;
  }

  Second try

  not solved · 5 of 10 testsanswer in 3.4 s · $0.0003

  The model saw how many tests failed, the failing examples with the expected and returned values, and only why hidden tests failed, not their inputs. Doesn't count for places or the rating.

  ✓	range_add_sum([1, 2, 3, 4], [["sum", 0, 3], ["add", 1, 2, 10], ["sum", 0, 1], ["sum", 2, 3]])expected [10, 13, 17]	2 ms
  ✗	range_add_sum([5], [["add", 0, 0, -5], ["sum", 0, 0]])expected [0]returned [-5]	<1 ms

  ✓ 2 ms✓ 4 ms✗ wrong answer✓ <1 ms✓ <1 ms✗ wrong answer⏱ wrong answer⏱ wrong answer

  Code

  function range_add_sum(nums, ops) {
    const n = nums.length;
    const size = Math.max(1, Math.ceil(Math.sqrt(n)));
    const blocks = Math.ceil(n / size);
    const sums = new Float64Array(blocks);
    const lazy = new Float64Array(blocks);
  
    for (let i = 0; i < n; i++) sums[Math.floor(i / size)] += nums[i];
  
    function rangeSum(l, r) {
      let total = 0;
      let i = l;
      while (i <= r) {
        const b = Math.floor(i / size);
        const start = b * size;
        const end = Math.min(n - 1, start + size - 1);
        if (i === start && end <= r) {
          total += sums[b] + lazy[b] * (end - start + 1);
          i = end + 1;
        } else {
          total += nums[i] + lazy[b];
          i++;
        }
      }
      return total;
    }
  
    const result = [];
    for (const op of ops) {
      const l = op[1], r = op[2];
      if (op[0] === "sum") {
        result.push(rangeSum(l, r));
      } else {
        const v = op[3];
        let i = l;
        while (i <= r) {
          const b = Math.floor(i / size);
          const start = b * size;
          const end = Math.min(n - 1, start + size - 1);
          if (i === start && end <= r) {
            sums[b] += v * (end - start + 1);
            lazy[b] += v;
            i = end + 1;
          } else {
            nums[i] += v;
            sums[b] += v;
            i++;
          }
        }
      }
    }
    return result;
  }

• #4MoonshotAI Kimi K2.7 Codenot solved · 0 of 10 testsanswer in 53 s · runtime <1 ms · $0.02

  SyntaxError: Unexpected token ';'

  ✗	range_add_sum([1, 2, 3, 4], [["sum", 0, 3], ["add", 1, 2, 10], ["sum", 0, 1], ["sum", 2, 3]])expected [10, 13, 17]SyntaxError: Unexpected token ';'	—
  ✗	range_add_sum([5], [["add", 0, 0, -5], ["sum", 0, 0]])expected [0]SyntaxError: Unexpected token ';'	—

  ✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError⏱ SyntaxError⏱ SyntaxError
  Code

  /**
   * @param {number[]} nums
   * @param {Array[]} ops
   * @returns {number[]}
   */
  function range_add_sum(nums, ops) {
      const n = nums.length;
      const ans = [];
      if (n === 0) return ans;
  
      const size = n + 5; // extra room for r+1 updates
      const b1 = new Array(size).fill(0);
      const b2 = new Array(size).fill(0);
  
      function add(bit, idx, val) {
          for (let i = idx; i < size; i += i & -i) {
              bit[i] += val;
          }
      }
  
      function sum(bit, idx) {
          let s = 0;
          for (let i = idx; i > 0; i -= i & -i) {
              s += bit[i];
          }
          return s;
      }
  
      function rangeAdd(l, r, v) {
          add(b1, l, v);
          add(b1, r + 1, -v);
          add(b2, l, v * (l - 1));
          add(b2, r + 1, -v * r);
      }
  
      function prefix(idx) {
          return sum(b1, idx) * idx - sum(b2, idx);
      }
  
      function rangeSum(l, r) {
          return prefix(r) - prefix(l - 1);
      }
  
      // initialize with the original array values
      for (let i =

  Second try

  solved · 10 of 10 testsanswer in 16 s · $0.0035

  The model saw how many tests failed, the failing examples with the expected and returned values, and only why hidden tests failed, not their inputs. Doesn't count for places or the rating.

  ✓	range_add_sum([1, 2, 3, 4], [["sum", 0, 3], ["add", 1, 2, 10], ["sum", 0, 1], ["sum", 2, 3]])expected [10, 13, 17]	2 ms
  ✓	range_add_sum([5], [["add", 0, 0, -5], ["sum", 0, 0]])expected [0]	1 ms

  ✓ 3 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ <1 ms✓ <1 ms⏱ 359 ms⏱ 455 ms

  Code

  /**
   * @param {number[]} nums
   * @param {Array[]} ops
   * @returns {number[]}
   */
  function range_add_sum(nums, ops) {
      const n = nums.length;
      const ans = [];
      if (n === 0) return ans;
  
      const size = n + 5;
      const b1 = new Array(size).fill(0);
      const b2 = new Array(size).fill(0);
  
      function add(bit, idx, val) {
          for (let i = idx; i < size; i += i & -i) {
              bit[i] += val;
          }
      }
  
      function sum(bit, idx) {
          let s = 0;
          for (let i = idx; i > 0; i -= i & -i) {
              s += bit[i];
          }
          return s;
      }
  
      function rangeAdd(l, r, v) {
          l++;
          r++;
          add(b1, l, v);
          add(b1, r + 1, -v);
          add(b2, l, v * (l - 1));
          add(b2, r + 1, -v * r);
      }
  
      function prefix(idx) {
          return sum(b1, idx) * idx - sum(b2, idx);
      }
  
      function rangeSum(l, r) {
          return prefix(r + 1) - prefix(l);
      }
  
      for (let i = 0; i < n; i++) {
          rangeAdd(i, i, nums[i]);
      }
  
      for (let i = 0; i < ops.length; i++) {
          const op = ops[i];
          if (op[0] === "add") {
              rangeAdd(op[1], op[2], op[3]);
          } else {
              ans.push(rangeSum(op[1], op[2]));
          }
      }
  
      return ans;
  }

Tokens cost: $0.02 · How rounds are run and scored →