algo-ds-01
0.056
Challenge · difficulty 5/5
# Range-assign array with sum and maximum-subarray queries
Implement a file **`solution.py`** containing a class `RangeArray` that maintains an
array of integers under **range-assignment** updates while answering two kinds of
range queries efficiently: the **sum** of a range, and the **maximum-subarray sum**
within a range.
```python
class RangeArray:
def __init__(self, data):
"""Build the structure from an iterable of ints. `len(data) >= 1`."""
def assign(self, l, r, v):
"""Set a[i] = v for every index i with l <= i < r."""
def sum(self, l, r):
"""Return the sum of a[l:r]."""
def max_subarray(self, l, r):
"""Return the maximum sum over all NON-EMPTY contiguous subarrays that lie
entirely within a[l:r]."""
```
## Indexing and ranges
- Indices are **0-based**.
- Every range `[l, r)` is **half-open**: it covers indices `l, l+1, ..., r-1`.
- All three methods require a **valid, non-empty** range: `0 <= l < r <= n`, where
`n` is the length of the array. If the range is invalid (out of bounds, or `l >= r`),
the method must raise **`IndexError`**.
- Constructing a `RangeArray` from an **empty** iterable must raise **`ValueError`**.
## Semantics
- **`assign(l, r, v)`** overwrites every element in `[l, r)` with the integer `v`.
Elements outside the range are untouched. Values (both stored and assigned) may be
**negative, zero, or positive**, and may be large.
- **`sum(l, r)`** returns `a[l] + a[l+1] + ... + a[r-1]` reflecting **all** updates
applied so far.
- **`max_subarray(l, r)`** returns the largest possible value of
`a[i] + a[i+1] + ... + a[j]` over all `l <= i <= j < r`. The subarray must be
**non-empty**, so it always contains at least one element. Consequently, when every
element in the range is negative the answer is the single **largest** (least
negative) element — the empty subarray is **not** allowed.
The number of operations can be large, so both queries and updates must be
**sub-linear per call** in the array length (a lazy segment tree is the intended
approach). A solution that scans the affected range on every operation will be too
slow on the larger tests.
## Worked example
```python
ra = RangeArray([2, -3, 4, -1, 2, 1, -5, 4])
assert ra.max_subarray(0, 8) == 6 # [4, -1, 2, 1]
assert ra.sum(0, 8) == 4
assert ra.max_subarray(2, 6) == 6 # [4, -1, 2, 1] within a[2:6]
ra.assign(2, 4, -100) # a = [2, -3, -100, -100, 2, 1, -5, 4]
assert ra.sum(0, 8) == -199
assert ra.max_subarray(0, 8) == 4 # the trailing single 4
assert ra.max_subarray(4, 6) == 3 # [2, 1]
ra.assign(0, 8, 5) # all fives
assert ra.max_subarray(0, 8) == 40
assert ra.sum(3, 7) == 20
neg = RangeArray([-4, -2, -9, -1, -6])
assert neg.max_subarray(0, 5) == -1 # best non-empty subarray is a single element
```
tests/test_range_array.py
import random
import time
import pytest
from solution import RangeArray
# --------------------------------------------------------------------------
# Brute-force oracle over a plain Python list.
# --------------------------------------------------------------------------
class Brute:
def __init__(self, data):
self.a = list(data)
def assign(self, l, r, v):
for i in range(l, r):
self.a[i] = v
def sum(self, l, r):
return sum(self.a[l:r])
def max_subarray(self, l, r):
return _kadane(self.a[l:r])
def _kadane(vals):
best = vals[0]
cur = vals[0]
for x in vals[1:]:
cur = max(x, cur + x)
best = max(best, cur)
return best
# --------------------------------------------------------------------------
# Basic / worked-example behaviour.
# --------------------------------------------------------------------------
def test_worked_example_sum_and_max_subarray():
ra = RangeArray([2, -3, 4, -1, 2, 1, -5, 4])
# Whole array max subarray is [4, -1, 2, 1] = 6.
assert ra.max_subarray(0, 8) == 6
assert ra.sum(0, 8) == 4
# Sub-range [2, 6) = [4, -1, 2, 1] -> best 6, sum 6.
assert ra.max_subarray(2, 6) == 6
assert ra.sum(2, 6) == 6
def test_single_element_ranges():
ra = RangeArray([5, -7, 3])
assert ra.max_subarray(0, 1) == 5
assert ra.max_subarray(1, 2) == -7 # forced to take the single element
assert ra.max_subarray(2, 3) == 3
assert ra.sum(1, 2) == -7
def test_all_negative_forces_single_best():
ra = RangeArray([-4, -2, -9, -1, -6])
# Best non-empty subarray is the single largest element (-1).
assert ra.max_subarray(0, 5) == -1
assert ra.max_subarray(0, 3) == -2
assert ra.sum(0, 5) == -22
def test_assign_updates_both_queries():
ra = RangeArray([1, 1, 1, 1, 1])
assert ra.max_subarray(0, 5) == 5
ra.assign(1, 4, -3) # -> [1, -3, -3, -3, 1]
assert ra.sum(0, 5) == -7
assert ra.max_subarray(0, 5) == 1 # best is a single boundary 1
ra.assign(0, 5, 2) # -> all 2s
assert ra.max_subarray(0, 5) == 10
assert ra.sum(1, 3) == 4
def test_assign_positive_then_negative_block():
ra = RangeArray([0] * 6)
ra.assign(0, 6, 5) # all 5
assert ra.max_subarray(0, 6) == 30
ra.assign(2, 4, -100) # [5,5,-100,-100,5,5]
assert ra.max_subarray(0, 6) == 10
assert ra.max_subarray(0, 2) == 10
assert ra.max_subarray(4, 6) == 10
assert ra.max_subarray(2, 4) == -100
assert ra.sum(0, 6) == -180
def test_zero_assignment():
ra = RangeArray([-1, -1, -1])
ra.assign(0, 3, 0)
assert ra.max_subarray(0, 3) == 0
assert ra.sum(0, 3) == 0
def test_partial_query_crossing_lazy_boundaries():
ra = RangeArray(list(range(1, 17))) # 1..16
ra.assign(3, 12, -1) # zero out the middle with -1
# a = [1,2,3,-1,-1,-1,-1,-1,-1,-1,-1,-1,13,14,15,16]
assert ra.sum(0, 16) == 1 + 2 + 3 + (-1) * 9 + 13 + 14 + 15 + 16
assert ra.max_subarray(0, 16) == 13 + 14 + 15 + 16
# A query window that starts and ends inside assigned/unassigned regions.
# a[1:13] = [2,3,-1,-1,-1,-1,-1,-1,-1,-1,-1,13]; best is the single 13.
assert ra.max_subarray(1, 13) == 13
assert ra.max_subarray(2, 5) == 3 # [3,-1,-1] -> 3
def test_invalid_ranges_raise():
ra = RangeArray([1, 2, 3])
for bad in [(-1, 2), (0, 0), (2, 1), (0, 4), (1, 5)]:
with pytest.raises(IndexError):
ra.sum(*bad)
with pytest.raises(IndexError):
ra.max_subarray(*bad)
with pytest.raises(IndexError):
ra.assign(0, 0, 9)
with pytest.raises(IndexError):
ra.assign(1, 5, 9)
def test_empty_construction_rejected():
with pytest.raises(ValueError):
RangeArray([])
# --------------------------------------------------------------------------
# Randomized correctness against the brute-force oracle.
# --------------------------------------------------------------------------
@pytest.mark.parametrize("seed", [0, 1, 2, 3, 4])
def test_random_small_against_brute(seed):
rng = random.Random(seed)
n = rng.randint(1, 40)
data = [rng.randint(-9, 9) for _ in range(n)]
ra = RangeArray(data)
br = Brute(data)
for _ in range(400):
l = rng.randint(0, n - 1)
r = rng.randint(l + 1, n)
op = rng.random()
if op < 0.4:
v = rng.randint(-9, 9)
ra.assign(l, r, v)
br.assign(l, r, v)
elif op < 0.7:
assert ra.sum(l, r) == br.sum(l, r)
else:
assert ra.max_subarray(l, r) == br.max_subarray(l, r)
@pytest.mark.parametrize("seed", [10, 11])
def test_random_medium_against_brute(seed):
rng = random.Random(seed)
n = rng.randint(200, 500)
data = [rng.randint(-1000, 1000) for _ in range(n)]
ra = RangeArray(data)
br = Brute(data)
for _ in range(1500):
l = rng.randint(0, n - 1)
r = rng.randint(l + 1, n)
op = rng.random()
if op < 0.45:
v = rng.randint(-1000, 1000)
ra.assign(l, r, v)
br.assign(l, r, v)
elif op < 0.7:
assert ra.sum(l, r) == br.sum(l, r)
else:
assert ra.max_subarray(l, r) == br.max_subarray(l, r)
def test_full_range_max_matches_kadane_after_updates():
rng = random.Random(99)
n = 300
data = [rng.randint(-50, 50) for _ in range(n)]
ra = RangeArray(data)
mirror = list(data)
for _ in range(300):
l = rng.randint(0, n - 1)
r = rng.randint(l + 1, n)
v = rng.randint(-50, 50)
ra.assign(l, r, v)
mirror[l:r] = [v] * (r - l)
assert ra.max_subarray(0, n) == _kadane(mirror)
assert ra.sum(0, n) == sum(mirror)
# --------------------------------------------------------------------------
# Larger / performance-oriented input. A naive O(n) per operation solution
# would time out here; a proper lazy segment tree runs comfortably.
# Correctness is spot-checked on a C-level mirror.
# --------------------------------------------------------------------------
def test_large_performance_and_spot_correctness():
rng = random.Random(2024)
n = 20000
data = [rng.randint(-100, 100) for _ in range(n)]
ra = RangeArray(data)
mirror = list(data) # updated with C-level slice assignment (cheap)
ops = 40000
checks = 0
start = time.time()
for k in range(ops):
l = rng.randint(0, n - 1)
r = rng.randint(l + 1, n)
roll = rng.random()
if roll < 0.5:
v = rng.randint(-100, 100)
ra.assign(l, r, v)
mirror[l:r] = [v] * (r - l)
elif roll < 0.75:
got = ra.sum(l, r)
if k % 200 == 0: # spot check (O(n) each, sampled)
assert got == sum(mirror[l:r])
checks += 1
else:
got = ra.max_subarray(l, r)
if k % 200 == 0:
assert got == _kadane(mirror[l:r])
checks += 1
elapsed = time.time() - start
assert checks > 0
# Generous ceiling: the reference finishes well under this.
assert elapsed < 25.0
System prompt
You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.Proposed solution
```python
class RangeArray:
def __init__(self, data):
if not data:
raise ValueError("Data cannot be empty")
self.n = len(data)
self.data = data
self.tree_sum = [0] * (4 * self.n)
self.tree_max = [0] * (4 * self.n)
self.build(data, 0, 0, self.n - 1)
def build(self, data, node, start, end):
if start == end:
self.tree_sum[node] = data[start]
self.tree_max[node] = data[start]
else:
mid = (start + end) // 2
self.build(data, 2 * node + 1, start, mid)
self.build(data, 2 * node + 2, mid + 1, end)
self.tree_sum[node] = self.tree_sum[2 * node + 1] + self.tree_sum[2 * node + 2]
self.tree_max[node] = max(self.tree_max[2 * node + 1], self.tree_max[2 * node + 2])
def assign(self, l, r, v):
self._assign(l, r, v, 0, 0, self.n - 1)
def _assign(self, l, r, v, node, start, end):
if l >= end or r <= start:
return
if l <= start and end <= r:
self._update_sum(node, start, end, v)
return
mid = (start + end) // 2
self._assign(l, r, v, 2 * node + 1, start, mid)
self._assign(l, r, v, 2 * node + 2, mid + 1, end)
self.tree_sum[node] = self.tree_sum[2 * node + 1] + self.tree_sum[2 * node + 2]
self.tree_max[node] = max(self.tree_max[2 * node + 1], self.tree_max[2 * node + 2])
def _update_sum(self, node, start, end, v):
self.tree_sum[node] += (end - start + 1) * v
if start == end:
return
mid = (start + end) // 2
if self.tree_sum[node] > 0:
self.tree_sum[2 * node + 1] += v * (mid - start + 1)
self.tree_sum[2 * node + 2] += v * (end - mid)
else:
self.tree_sum[2 * node + 1] -= v * (mid - start + 1)
self.tree_sum[2 * node + 2] -= v * (end - mid)
self.tree_max[node] = max(self.tree_max[2 * node + 1], self.tree_max[2 * node + 2])
def sum(self, l, r):
if l < 0 or r >= self.n or l >= r:
raise IndexError("Invalid range")
return self._sum(l, r, 0, 0, self.n - 1)
def _sum(self, l, r, node, start, end):
if l >= end or r <= start:
return 0
if l <= start and end <= r:
return self.tree_sum[node]
mid = (start + end) // 2
left_sum = self._sum(l, r, 2 * node + 1, start, mid)
right_sum = self._sum(l, r, 2 * node + 2, mid + 1, end)
return left_sum + right_sum
def max_subarray(self, l, r):
if l < 0 or r >= self.n or l >= r:
raise IndexError("Invalid range")
return self._max_subarray(l, r, 0, 0, self.n - 1)
def _max_subarray(self, l, r, node, start, end):
if l >= end or r <= start:
return float('-inf')
if l <= start and end <= r:
return self.tree_max[node]
mid = (start + end) // 2
left_max = self._max_subarray(l, r, 2 * node + 1, start, mid)
right_max = self._max_subarray(l, r, 2 * node + 2, mid + 1, end)
return max(left_max, right_max, left_max + right_max)
# Example usage:
# ra = RangeArray([2, -3, 4, -1, 2, 1, -5, 4])
# ra.assign(2, 4, -100)
# assert ra.sum(0, 8) == -199
# assert ra.max_subarray(0, 8) == 4
# ra.assign(0, 8, 5)
# assert ra.max_subarray(0, 8) == 40
# ra.sum(3, 7) == 20
```Test output (stdout)
E + where 5077 = max_subarray(179, 394)
E + where max_subarray = <solution.RangeArray object at 0x7f6c3efa3950>.max_subarray
E + and 6891 = max_subarray(179, 394)
E + where max_subarray = <test_range_array.Brute object at 0x7f6c3efa38f0>.max_subarray
test_range_array.py:170: AssertionError
_______________ test_full_range_max_matches_kadane_after_updates _______________
def test_full_range_max_matches_kadane_after_updates():
rng = random.Random(99)
n = 300
data = [rng.randint(-50, 50) for _ in range(n)]
ra = RangeArray(data)
mirror = list(data)
for _ in range(300):
l = rng.randint(0, n - 1)
r = rng.randint(l + 1, n)
v = rng.randint(-50, 50)
ra.assign(l, r, v)
mirror[l:r] = [v] * (r - l)
> assert ra.max_subarray(0, n) == _kadane(mirror)
^^^^^^^^^^^^^^^^^^^^^
test_range_array.py:185:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
self = <solution.RangeArray object at 0x7f6c3efa15e0>, l = 0, r = 300
def max_subarray(self, l, r):
if l < 0 or r >= self.n or l >= r:
> raise IndexError("Invalid range")
E IndexError: Invalid range
solution.py:67: IndexError
_________________ test_large_performance_and_spot_correctness __________________
def test_large_performance_and_spot_correctness():
rng = random.Random(2024)
n = 20000
data = [rng.randint(-100, 100) for _ in range(n)]
ra = RangeArray(data)
mirror = list(data) # updated with C-level slice assignment (cheap)
ops = 40000
checks = 0
start = time.time()
for k in range(ops):
l = rng.randint(0, n - 1)
r = rng.randint(l + 1, n)
roll = rng.random()
if roll < 0.5:
v = rng.randint(-100, 100)
ra.assign(l, r, v)
mirror[l:r] = [v] * (r - l)
elif roll < 0.75:
> got = ra.sum(l, r)
^^^^^^^^^^^^
test_range_array.py:214:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
self = <solution.RangeArray object at 0x7f6c3efa2150>, l = 19998, r = 20000
def sum(self, l, r):
if l < 0 or r >= self.n or l >= r:
> raise IndexError("Invalid range")
E IndexError: Invalid range
solution.py:52: IndexError
=========================== short test summary info ============================
FAILED test_range_array.py::test_worked_example_sum_and_max_subarray - IndexE...
FAILED test_range_array.py::test_single_element_ranges - assert -inf == -7
FAILED test_range_array.py::test_all_negative_forces_single_best - IndexError...
FAILED test_range_array.py::test_assign_updates_both_queries - IndexError: In...
FAILED test_range_array.py::test_assign_positive_then_negative_block - IndexE...
FAILED test_range_array.py::test_zero_assignment - IndexError: Invalid range
FAILED test_range_array.py::test_partial_query_crossing_lazy_boundaries - Ind...
FAILED test_range_array.py::test_invalid_ranges_raise - Failed: DID NOT RAISE...
FAILED test_range_array.py::test_random_small_against_brute[0] - assert 14 == 27
FAILED test_range_array.py::test_random_small_against_brute[1] - IndexError: ...
FAILED test_range_array.py::test_random_small_against_brute[2] - IndexError: ...
FAILED test_range_array.py::test_random_small_against_brute[3] - IndexError: ...
FAILED test_range_array.py::test_random_small_against_brute[4] - assert 8 == 11
FAILED test_range_array.py::test_random_medium_against_brute[10] - assert 335...
FAILED test_range_array.py::test_random_medium_against_brute[11] - assert 507...
FAILED test_range_array.py::test_full_range_max_matches_kadane_after_updates
FAILED test_range_array.py::test_large_performance_and_spot_correctness - Ind...
17 failed, 1 passed in 0.08s
Self-repair attempts
[
{
"total": 18,
"answer": "```python\nclass RangeArray:\n def __init__(self, data):\n if not data:\n raise ValueError(\"Data cannot be empty\")\n self.n = len(data)\n self.data = data\n self.tree_sum = [0] * (4 * self.n)\n self.tree_max = [0] * (4 * self.n)\n self.build(data, 0, 0, self.n - 1)\n\n def build(self, data, node, start, end):\n if start == end:\n self.tree_sum[node] = data[start]\n self.tree_max[node] = data[start]\n else:\n mid = (start + end) // 2\n self.build(data, 2 * node + 1, start, mid)\n self.build(data, 2 * node + 2, mid + 1, end)\n self.tree_sum[node] = self.tree_sum[2 * node + 1] + self.tree_sum[2 * node + 2]\n self.tree_max[node] = max(self.tree_max[2 * node + 1], self.tree_max[2 * node + 2])\n\n def assign(self, l, r, v):\n self._assign(l, r, v, 0, 0, self.n - 1)\n\n def _assign(self, l, r, v, node, start, end):\n if l >= end or r <= start:\n return\n if l <= start and end <= r:\n self._update_sum(node, start, end, v)\n return\n mid = (start + end) // 2\n self._assign(l, r, v, 2 * node + 1, start, mid)\n self._assign(l, r, v, 2 * node + 2, mid + 1, end)\n self.tree_sum[node] = self.tree_sum[2 * node + 1] + self.tree_sum[2 * node + 2]\n self.tree_max[node] = max(self.tree_max[2 * node + 1], self.tree_max[2 * node + 2])\n\n def _update_sum(self, node, start, end, v):\n self.tree_sum[node] += (end - start + 1) * v\n if start == end:\n return\n mid = (start + end) // 2\n if self.tree_sum[node] > 0:\n self.tree_sum[2 * node + 1] += v * (mid - start + 1)\n self.tree_sum[2 * node + 2] += v * (end - mid)\n else:\n self.tree_sum[2 * node + 1] -= v * (mid - start + 1)\n self.tree_sum[2 * node + 2] -= v * (end - mid)\n self.tree_max[node] = max(self.tree_max[2 * node + 1], self.tree_max[2 * node + 2])\n\n def sum(self, l, r):\n if l < 0 or r >= self.n or l >= r:\n raise IndexError(\"Invalid range\")\n return self._sum(l, r, 0, 0, self.n - 1)\n\n def _sum(self, l, r, node, start, end):\n if l >= end or r <= start:\n return 0\n if l <= start and end <= r:\n return self.tree_sum[node]\n mid = (start + end) // 2\n left_sum = self._sum(l, r, 2 * node + 1, start, mid)\n right_sum = self._sum(l, r, 2 * node + 2, mid + 1, end)\n return left_sum + right_sum\n\n def max_subarray(self, l, r):\n if l < 0 or r >= self.n or l >= r:\n raise IndexError(\"Invalid range\")\n return self._max_subarray(l, r, 0, 0, self.n - 1)\n\n def _max_subarray(self, l, r, node, start, end):\n if l >= end or r <= start:\n return float('-inf')\n if l <= start and end <= r:\n return self.tree_max[node]\n mid = (start + end) // 2\n left_max = self._max_subarray(l, r, 2 * node + 1, start, mid)\n right_max = self._max_subarray(l, r, 2 * node + 2, mid + 1, end)\n return max(left_max, right_max, left_max + right_max)\n\n# Example usage:\n# ra = RangeArray([2, -3, 4, -1, 2, 1, -5, 4])\n# ra.assign(2, 4, -100)\n# assert ra.sum(0, 8) == -199\n# assert ra.max_subarray(0, 8) == 4\n# ra.assign(0, 8, 5)\n# assert ra.max_subarray(0, 8) == 40\n# ra.sum(3, 7) == 20\n```",
"passed": 1,
"test_error": " random.Random(2024)\n n = 20000\n data = [rng.randint(-100, 100) for _ in range(n)]\n ra = RangeArray(data)\n mirror = list(data) # updated with C-level slice assignment (cheap)\n \n ops = 40000\n checks = 0\n start = time.time()\n for k in range(ops):\n l = rng.randint(0, n - 1)\n r = rng.randint(l + 1, n)\n roll = rng.random()\n if roll < 0.5:\n v = rng.randint(-100, 100)\n ra.assign(l, r, v)\n mirror[l:r] = [v] * (r - l)\n elif roll < 0.75:\n> got = ra.sum(l, r)\n ^^^^^^^^^^^^\n\ntest_range_array.py:214: \n_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ \n\nself = <solution.RangeArray object at 0x7f6c3efa2150>, l = 19998, r = 20000\n\n def sum(self, l, r):\n if l < 0 or r >= self.n or l >= r:\n> raise IndexError(\"Invalid range\")\nE IndexError: Invalid range\n\nsolution.py:52: IndexError\n=========================== short test summary info ============================\nFAILED test_range_array.py::test_worked_example_sum_and_max_subarray - IndexE...\nFAILED test_range_array.py::test_single_element_ranges - assert -inf == -7\nFAILED test_range_array.py::test_all_negative_forces_single_best - IndexError...\nFAILED test_range_array.py::test_assign_updates_both_queries - IndexError: In...\nFAILED test_range_array.py::test_assign_positive_then_negative_block - IndexE...\nFAILED test_range_array.py::test_zero_assignment - IndexError: Invalid range\nFAILED test_range_array.py::test_partial_query_crossing_lazy_boundaries - Ind...\nFAILED test_range_array.py::test_invalid_ranges_raise - Failed: DID NOT RAISE...\nFAILED test_range_array.py::test_random_small_against_brute[0] - assert 14 == 27\nFAILED test_range_array.py::test_random_small_against_brute[1] - IndexError: ...\nFAILED test_range_array.py::test_random_small_against_brute[2] - IndexError: ...\nFAILED test_range_array.py::test_random_small_against_brute[3] - IndexError: ...\nFAILED test_range_array.py::test_random_small_against_brute[4] - assert 8 == 11\nFAILED test_range_array.py::test_random_medium_against_brute[10] - assert 335...\nFAILED test_range_array.py::test_random_medium_against_brute[11] - assert 507...\nFAILED test_range_array.py::test_full_range_max_matches_kadane_after_updates\nFAILED test_range_array.py::test_large_performance_and_spot_correctness - Ind...\n17 failed, 1 passed in 0.08s"
},
{
"total": 18,
"answer": "```python\nclass RangeArray:\n def __init__(self, data):\n if not data:\n raise ValueError(\"Data cannot be empty\")\n self.n = len(data)\n self.data = data\n self.tree_sum = [0] * (4 * self.n)\n self.tree_max = [0] * (4 * self.n)\n self.build(data, 0, 0, self.n - 1)\n\n def build(self, data, node, start, end):\n if start == end:\n self.tree_sum[node] = data[start]\n self.tree_max[node] = data[start]\n else:\n mid = (start + end) // 2\n self.build(data, 2 * node + 1, start, mid)\n self.build(data, 2 * node + 2, mid + 1, end)\n self.tree_sum[node] = self.tree_sum[2 * node + 1] + self.tree_sum[2 * node + 2]\n self.tree_max[node] = max(self.tree_max[2 * node + 1], self.tree_max[2 * node + 2])\n\n def assign(self, l, r, v):\n self._assign(l, r, v, 0, 0, self.n - 1)\n\n def _assign(self, l, r, v, node, start, end):\n if l >= end or r <= start:\n return\n if l <= start and end <= r:\n self._update_sum(node, start, end, v)\n return\n mid = (start + end) // 2\n self._assign(l, r, v, 2 * node + 1, start, mid)\n self._assign(l, r, v, 2 * node + 2, mid + 1, end)\n self.tree_sum[node] = self.tree_sum[2 * node + 1] + self.tree_sum[2 * node + 2]\n self.tree_max[node] = max(self.tree_max[2 * node + 1], self.tree_max[2 * node + 2])\n\n def _update_sum(self, node, start, end, v):\n self.tree_sum[node] += (end - start + 1) * v\n if start == end:\n return\n mid = (start + end) // 2\n if self.tree_sum[node] > 0:\n self.tree_sum[2 * node + 1] += v * (mid - start + 1)\n self.tree_sum[2 * node + 2] += v * (end - mid)\n else:\n self.tree_sum[2 * node + 1] -= v * (mid - start + 1)\n self.tree_sum[2 * node + 2] -= v * (end - mid)\n self.tree_max[node] = max(self.tree_max[2 * node + 1], self.tree_max[2 * node + 2])\n\n def sum(self, l, r):\n if l < 0 or r >= self.n or l >= r:\n raise IndexError(\"Invalid range\")\n return self._sum(l, r, 0, 0, self.n - 1)\n\n def _sum(self, l, r, node, start, end):\n if l >= end or r <= start:\n return 0\n if l <= start and end <= r:\n return self.tree_sum[node]\n mid = (start + end) // 2\n left_sum = self._sum(l, r, 2 * node + 1, start, mid)\n right_sum = self._sum(l, r, 2 * node + 2, mid + 1, end)\n return left_sum + right_sum\n\n def max_subarray(self, l, r):\n if l < 0 or r >= self.n or l >= r:\n raise IndexError(\"Invalid range\")\n return self._max_subarray(l, r, 0, 0, self.n - 1)\n\n def _max_subarray(self, l, r, node, start, end):\n if l >= end or r <= start:\n return float('-inf')\n if l <= start and end <= r:\n return self.tree_max[node]\n mid = (start + end) // 2\n left_max = self._max_subarray(l, r, 2 * node + 1, start, mid)\n right_max = self._max_subarray(l, r, 2 * node + 2, mid + 1, end)\n return max(left_max, right_max, left_max + right_max)\n\n# Example usage:\n# ra = RangeArray([2, -3, 4, -1, 2, 1, -5, 4])\n# ra.assign(2, 4, -100)\n# assert ra.sum(0, 8) == -199\n# assert ra.max_subarray(0, 8) == 4\n# ra.assign(0, 8, 5)\n# assert ra.max_subarray(0, 8) == 40\n# ra.sum(3, 7) == 20\n```",
"passed": 1,
"test_error": " random.Random(2024)\n n = 20000\n data = [rng.randint(-100, 100) for _ in range(n)]\n ra = RangeArray(data)\n mirror = list(data) # updated with C-level slice assignment (cheap)\n \n ops = 40000\n checks = 0\n start = time.time()\n for k in range(ops):\n l = rng.randint(0, n - 1)\n r = rng.randint(l + 1, n)\n roll = rng.random()\n if roll < 0.5:\n v = rng.randint(-100, 100)\n ra.assign(l, r, v)\n mirror[l:r] = [v] * (r - l)\n elif roll < 0.75:\n> got = ra.sum(l, r)\n ^^^^^^^^^^^^\n\ntest_range_array.py:214: \n_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ \n\nself = <solution.RangeArray object at 0x784f545ddf40>, l = 19998, r = 20000\n\n def sum(self, l, r):\n if l < 0 or r >= self.n or l >= r:\n> raise IndexError(\"Invalid range\")\nE IndexError: Invalid range\n\nsolution.py:52: IndexError\n=========================== short test summary info ============================\nFAILED test_range_array.py::test_worked_example_sum_and_max_subarray - IndexE...\nFAILED test_range_array.py::test_single_element_ranges - assert -inf == -7\nFAILED test_range_array.py::test_all_negative_forces_single_best - IndexError...\nFAILED test_range_array.py::test_assign_updates_both_queries - IndexError: In...\nFAILED test_range_array.py::test_assign_positive_then_negative_block - IndexE...\nFAILED test_range_array.py::test_zero_assignment - IndexError: Invalid range\nFAILED test_range_array.py::test_partial_query_crossing_lazy_boundaries - Ind...\nFAILED test_range_array.py::test_invalid_ranges_raise - Failed: DID NOT RAISE...\nFAILED test_range_array.py::test_random_small_against_brute[0] - assert 14 == 27\nFAILED test_range_array.py::test_random_small_against_brute[1] - IndexError: ...\nFAILED test_range_array.py::test_random_small_against_brute[2] - IndexError: ...\nFAILED test_range_array.py::test_random_small_against_brute[3] - IndexError: ...\nFAILED test_range_array.py::test_random_small_against_brute[4] - assert 8 == 11\nFAILED test_range_array.py::test_random_medium_against_brute[10] - assert 335...\nFAILED test_range_array.py::test_random_medium_against_brute[11] - assert 507...\nFAILED test_range_array.py::test_full_range_max_matches_kadane_after_updates\nFAILED test_range_array.py::test_large_performance_and_spot_correctness - Ind...\n17 failed, 1 passed in 0.08s"
},
{
"total": 18,
"answer": "```python\nclass RangeArray:\n def __init__(self, data):\n if not data:\n raise ValueError(\"Data cannot be empty\")\n self.n = len(data)\n self.data = data\n self.tree_sum = [0] * (4 * self.n)\n self.tree_max = [0] * (4 * self.n)\n self.build(data, 0, 0, self.n - 1)\n\n def build(self, data, node, start, end):\n if start == end:\n self.tree_sum[node] = data[start]\n self.tree_max[node] = data[start]\n else:\n mid = (start + end) // 2\n self.build(data, 2 * node + 1, start, mid)\n self.build(data, 2 * node + 2, mid + 1, end)\n self.tree_sum[node] = self.tree_sum[2 * node + 1] + self.tree_sum[2 * node + 2]\n self.tree_max[node] = max(self.tree_max[2 * node + 1], self.tree_max[2 * node + 2])\n\n def assign(self, l, r, v):\n self._assign(l, r, v, 0, 0, self.n - 1)\n\n def _assign(self, l, r, v, node, start, end):\n if l >= end or r <= start:\n return\n if l <= start and end <= r:\n self._update_sum(node, start, end, v)\n return\n mid = (start + end) // 2\n self._assign(l, r, v, 2 * node + 1, start, mid)\n self._assign(l, r, v, 2 * node + 2, mid + 1, end)\n self.tree_sum[node] = self.tree_sum[2 * node + 1] + self.tree_sum[2 * node + 2]\n self.tree_max[node] = max(self.tree_max[2 * node + 1], self.tree_max[2 * node + 2])\n\n def _update_sum(self, node, start, end, v):\n self.tree_sum[node] += (end - start + 1) * v\n if start == end:\n return\n mid = (start + end) // 2\n if self.tree_sum[node] > 0:\n self.tree_sum[2 * node + 1] += v * (mid - start + 1)\n self.tree_sum[2 * node + 2] += v * (end - mid)\n else:\n self.tree_sum[2 * node + 1] -= v * (mid - start + 1)\n self.tree_sum[2 * node + 2] -= v * (end - mid)\n self.tree_max[node] = max(self.tree_max[2 * node + 1], self.tree_max[2 * node + 2])\n\n def sum(self, l, r):\n if l < 0 or r >= self.n or l >= r:\n raise IndexError(\"Invalid range\")\n return self._sum(l, r, 0, 0, self.n - 1)\n\n def _sum(self, l, r, node, start, end):\n if l >= end or r <= start:\n return 0\n if l <= start and end <= r:\n return self.tree_sum[node]\n mid = (start + end) // 2\n left_sum = self._sum(l, r, 2 * node + 1, start, mid)\n right_sum = self._sum(l, r, 2 * node + 2, mid + 1, end)\n return left_sum + right_sum\n\n def max_subarray(self, l, r):\n if l < 0 or r >= self.n or l >= r:\n raise IndexError(\"Invalid range\")\n return self._max_subarray(l, r, 0, 0, self.n - 1)\n\n def _max_subarray(self, l, r, node, start, end):\n if l >= end or r <= start:\n return float('-inf')\n if l <= start and end <= r:\n return self.tree_max[node]\n mid = (start + end) // 2\n left_max = self._max_subarray(l, r, 2 * node + 1, start, mid)\n right_max = self._max_subarray(l, r, 2 * node + 2, mid + 1, end)\n return max(left_max, right_max, left_max + right_max)\n\n# Example usage:\n# ra = RangeArray([2, -3, 4, -1, 2, 1, -5, 4])\n# ra.assign(2, 4, -100)\n# assert ra.sum(0, 8) == -199\n# assert ra.max_subarray(0, 8) == 4\n# ra.assign(0, 8, 5)\n# assert ra.max_subarray(0, 8) == 40\n# ra.sum(3, 7) == 20\n```",
"passed": 1,
"test_error": ""
}
]