任务 · 数据处理 困难 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]

• 第 1 名Google Gemini 3.8 Flash已解决 · 通过 10/10 个测试生成耗时 5.2 秒 · 执行耗时 544 毫秒 · $0.0032

  ✓	range_add_sum([1, 2, 3, 4], [["sum", 0, 3], ["add", 1, 2, 10], ["sum", 0, 1], ["sum", 2, 3]])预期 [10, 13, 17]	3 毫秒
  ✓	range_add_sum([5], [["add", 0, 0, -5], ["sum", 0, 0]])预期 [0]	1 毫秒

  ✓ 2 毫秒✓ <1 毫秒✓ 25 毫秒✓ 2 毫秒✓ 2 毫秒✓ 1 毫秒⏱ 360 毫秒⏱ 147 毫秒
  代码

  /**
   * @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;
  }

• 第 2 名DeepSeek V4.1 Flash已解决 · 通过 10/10 个测试生成耗时 1.5 秒 · 执行耗时 1.3 秒 · $0.0005

  ✓	range_add_sum([1, 2, 3, 4], [["sum", 0, 3], ["add", 1, 2, 10], ["sum", 0, 1], ["sum", 2, 3]])预期 [10, 13, 17]	2 毫秒
  ✓	range_add_sum([5], [["add", 0, 0, -5], ["sum", 0, 0]])预期 [0]	1 毫秒

  ✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒✓ 1 毫秒✓ 1 毫秒✓ 2 毫秒⏱ 727 毫秒⏱ 578 毫秒
  代码

  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;
  }

• 第 3 名OpenAI GPT-6 Luna未解决 · 通过 4/10 个测试生成耗时 4.1 秒 · 执行耗时 1.9 秒 · $0.0003

  ✓	range_add_sum([1, 2, 3, 4], [["sum", 0, 3], ["add", 1, 2, 10], ["sum", 0, 1], ["sum", 2, 3]])预期 [10, 13, 17]	3 毫秒
  ✗	range_add_sum([5], [["add", 0, 0, -5], ["sum", 0, 0]])预期 [0]返回 [-5]	<1 毫秒

  ✓ <1 毫秒✓ 3 毫秒✗ 答案错误✓ 1 毫秒✗ 答案错误✗ 答案错误⏱ 答案错误⏱ 答案错误
  代码

  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;
  }

  二次尝试

  未解决 · 通过 5/10 个测试生成耗时 3.4 秒 · $0.0003

  模型可以看到失败的测试数量、包含预期值和返回值的失败示例，以及隐藏测试未通过的原因（不含输入数据）。此成绩不计入排名或评分。

  ✓	range_add_sum([1, 2, 3, 4], [["sum", 0, 3], ["add", 1, 2, 10], ["sum", 0, 1], ["sum", 2, 3]])预期 [10, 13, 17]	2 毫秒
  ✗	range_add_sum([5], [["add", 0, 0, -5], ["sum", 0, 0]])预期 [0]返回 [-5]	<1 毫秒

  ✓ 2 毫秒✓ 4 毫秒✗ 答案错误✓ <1 毫秒✓ <1 毫秒✗ 答案错误⏱ 答案错误⏱ 答案错误

  代码

  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;
  }

• 第 4 名MoonshotAI Kimi K2.7 Code未解决 · 通过 0/10 个测试生成耗时 53 秒 · 执行耗时 <1 毫秒 · $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]])预期 [10, 13, 17]SyntaxError: Unexpected token ';'	—
  ✗	range_add_sum([5], [["add", 0, 0, -5], ["sum", 0, 0]])预期 [0]SyntaxError: Unexpected token ';'	—

  ✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError⏱ SyntaxError⏱ SyntaxError
  代码

  /**
   * @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 =

  二次尝试

  已解决 · 通过 10/10 个测试生成耗时 16 秒 · $0.0035

  模型可以看到失败的测试数量、包含预期值和返回值的失败示例，以及隐藏测试未通过的原因（不含输入数据）。此成绩不计入排名或评分。

  ✓	range_add_sum([1, 2, 3, 4], [["sum", 0, 3], ["add", 1, 2, 10], ["sum", 0, 1], ["sum", 2, 3]])预期 [10, 13, 17]	2 毫秒
  ✓	range_add_sum([5], [["add", 0, 0, -5], ["sum", 0, 0]])预期 [0]	1 毫秒

  ✓ 3 毫秒✓ 2 毫秒✓ 2 毫秒✓ 2 毫秒✓ <1 毫秒✓ <1 毫秒⏱ 359 毫秒⏱ 455 毫秒

  代码

  /**
   * @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;
  }

Token 成本: $0.02 · 轮次运行与评分规则 →