algo-ds-01

# 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
```

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

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.

```python
class RangeArray:
    class Node:
        __slots__ = ('l', 'r', 'sum', 'max_subarray', 'lazy_assign')
        def __init__(self, l, r):
            self.l = l
            self.r = r
            self.sum = 0
            self.max_subarray = float('-inf')
            self.lazy_assign = None

    def __init__(self, data):
        if not data:
            raise ValueError("Data cannot be empty")
        self.n = len(data)
        self.root = self._build(data, 0, self.n)

    def _build(self, data, l, r):
        node = self.Node(l, r)
        if r - l == 1:
            node.sum = data[l]
            node.max_subarray = data[l]
            return node
        mid = (l + r) // 2
        node.left = self._build(data, l, mid)
        node.right = self._build(data, mid, r)
        self._pull(node)
        return node

    def _pull(self, node):
        left = node.left
        right = node.right
        node.sum = left.sum + right.sum
        node.max_subarray = max(left.max_subarray, right.max_subarray, left.sum + right.max_subarray)

    def _apply_assign(self, node, v):
        node.sum = v * (node.r - node.l)
        node.max_subarray = v
        node.lazy_assign = v

    def _push(self, node):
        if node.lazy_assign is not None:
            self._apply_assign(node.left, node.lazy_assign)
            self._apply_assign(node.right, node.lazy_assign)
            node.lazy_assign = None

    def _assign(self, node, l, r, v):
        if node.r <= l or node.l >= r:
            return
        if l <= node.l and node.r <= r:
            self._apply_assign(node, v)
            return
        self._push(node)
        self._assign(node.left, l, r, v)
        self._assign(node.right, l, r, v)
        self._pull(node)

    def _query_sum(self, node, l, r):
        if node.r <= l or node.l >= r:
            return 0
        if l <= node.l and node.r <= r:
            return node.sum
        self._push(node)
        return self._query_sum(node.left, l, r) + self._query_sum(node.right, l, r)

    def _query_max_subarray(self, node, l, r):
        if node.r <= l or node.l >= r:
            return float('-inf')
        if l <= node.l and node.r <= r:
            return node.max_subarray
        self._push(node)
        left_max = self._query_max_subarray(node.left, l, r)
        right_max = self._query_max_subarray(node.right, l, r)
        mid_max = self._query_sum(node.left, l, r) + right_max
        return max(left_max, right_max, mid_max)

    def assign(self, l, r, v):
        if not (0 <= l < r <= self.n):
            raise IndexError("Invalid range")
        self._assign(self.root, l, r, v)

    def sum(self, l, r):
        if not (0 <= l < r <= self.n):
            raise IndexError("Invalid range")
        return self._query_sum(self.root, l, r)

    def max_subarray(self, l, r):
        if not (0 <= l < r <= self.n):
            raise IndexError("Invalid range")
        return self._query_max_subarray(self.root, l, r)
```

[
  {
    "total": 18,
    "answer": "```python\nclass RangeArray:\n    class Node:\n        __slots__ = ('l', 'r', 'sum', 'max_subarray', 'lazy_assign')\n        def __init__(self, l, r):\n            self.l = l\n            self.r = r\n            self.sum = 0\n            self.max_subarray = float('-inf')\n            self.lazy_assign = None\n\n    def __init__(self, data):\n        if not data:\n            raise ValueError(\"Data cannot be empty\")\n        self.n = len(data)\n        self.root = self._build(data, 0, self.n)\n\n    def _build(self, data, l, r):\n        node = self.Node(l, r)\n        if r - l == 1:\n            node.sum = data[l]\n            node.max_subarray = data[l]\n            return node\n        mid = (l + r) // 2\n        node.left = self._build(data, l, mid)\n        node.right = self._build(data, mid, r)\n        self._pull(node)\n        return node\n\n    def _pull(self, node):\n        left = node.left\n        right = node.right\n        node.sum = left.sum + right.sum\n        node.max_subarray = max(left.max_subarray, right.max_subarray, left.sum + right.max_subarray)\n\n    def _apply_assign(self, node, v):\n        node.sum = v * (node.r - node.l)\n        node.max_subarray = v\n        node.lazy_assign = v\n\n    def _push(self, node):\n        if node.lazy_assign is not None:\n            self._apply_assign(node.left, node.lazy_assign)\n            self._apply_assign(node.right, node.lazy_assign)\n            node.lazy_assign = None\n\n    def _assign(self, node, l, r, v):\n        if node.r <= l or node.l >= r:\n            return\n        if l <= node.l and node.r <= r:\n            self._apply_assign(node, v)\n            return\n        self._push(node)\n        self._assign(node.left, l, r, v)\n        self._assign(node.right, l, r, v)\n        self._pull(node)\n\n    def _query_sum(self, node, l, r):\n        if node.r <= l or node.l >= r:\n            return 0\n        if l <= node.l and node.r <= r:\n            return node.sum\n        self._push(node)\n        return self._query_sum(node.left, l, r) + self._query_sum(node.right, l, r)\n\n    def _query_max_subarray(self, node, l, r):\n        if node.r <= l or node.l >= r:\n            return float('-inf')\n        if l <= node.l and node.r <= r:\n            return node.max_subarray\n        self._push(node)\n        left_max = self._query_max_subarray(node.left, l, r)\n        right_max = self._query_max_subarray(node.right, l, r)\n        mid_max = self._query_sum(node.left, l, r) + right_max\n        return max(left_max, right_max, mid_max)\n\n    def assign(self, l, r, v):\n        if not (0 <= l < r <= self.n):\n            raise IndexError(\"Invalid range\")\n        self._assign(self.root, l, r, v)\n\n    def sum(self, l, r):\n        if not (0 <= l < r <= self.n):\n            raise IndexError(\"Invalid range\")\n        return self._query_sum(self.root, l, r)\n\n    def max_subarray(self, l, r):\n        if not (0 <= l < r <= self.n):\n            raise IndexError(\"Invalid range\")\n        return self._query_max_subarray(self.root, l, r)\n```",
    "passed": 1,
    "test_error": "^^^^^^^^^^^^^^^^^^\nsolution.py:24: in _build\n    node.left = self._build(data, l, mid)\n                ^^^^^^^^^^^^^^^^^^^^^^^^^\nsolution.py:24: in _build\n    node.left = self._build(data, l, mid)\n                ^^^^^^^^^^^^^^^^^^^^^^^^^\nsolution.py:24: in _build\n    node.left = self._build(data, l, mid)\n                ^^^^^^^^^^^^^^^^^^^^^^^^^\nsolution.py:24: in _build\n    node.left = self._build(data, l, mid)\n                ^^^^^^^^^^^^^^^^^^^^^^^^^\n_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ \n\nself = <solution.RangeArray object at 0x7b786a226e70>\ndata = [20, -54, 86, 48, -23, -49, ...], l = 0, r = 2\n\n    def _build(self, data, l, r):\n        node = self.Node(l, r)\n        if r - l == 1:\n            node.sum = data[l]\n            node.max_subarray = data[l]\n            return node\n        mid = (l + r) // 2\n>       node.left = self._build(data, l, mid)\n        ^^^^^^^^^\nE       AttributeError: 'Node' object has no attribute 'left'\n\nsolution.py:24: AttributeError\n=========================== short test summary info ============================\nFAILED test_range_array.py::test_worked_example_sum_and_max_subarray - Attrib...\nFAILED test_range_array.py::test_single_element_ranges - AttributeError: 'Nod...\nFAILED test_range_array.py::test_all_negative_forces_single_best - AttributeE...\nFAILED test_range_array.py::test_assign_updates_both_queries - AttributeError...\nFAILED test_range_array.py::test_assign_positive_then_negative_block - Attrib...\nFAILED test_range_array.py::test_zero_assignment - AttributeError: 'Node' obj...\nFAILED test_range_array.py::test_partial_query_crossing_lazy_boundaries - Att...\nFAILED test_range_array.py::test_invalid_ranges_raise - AttributeError: 'Node...\nFAILED test_range_array.py::test_random_small_against_brute[0] - AttributeErr...\nFAILED test_range_array.py::test_random_small_against_brute[1] - AttributeErr...\nFAILED test_range_array.py::test_random_small_against_brute[2] - AttributeErr...\nFAILED test_range_array.py::test_random_small_against_brute[3] - AttributeErr...\nFAILED test_range_array.py::test_random_small_against_brute[4] - AttributeErr...\nFAILED test_range_array.py::test_random_medium_against_brute[10] - AttributeE...\nFAILED test_range_array.py::test_random_medium_against_brute[11] - AttributeE...\nFAILED test_range_array.py::test_full_range_max_matches_kadane_after_updates\nFAILED test_range_array.py::test_large_performance_and_spot_correctness - Att...\n17 failed, 1 passed in 0.10s"
  },
  {
    "total": 18,
    "answer": "```python\nclass RangeArray:\n    class Node:\n        __slots__ = ('l', 'r', 'sum', 'max_subarray', 'lazy_assign', 'left', 'right')\n        def __init__(self, l, r):\n            self.l = l\n            self.r = r\n            self.sum = 0\n            self.max_subarray = float('-inf')\n            self.lazy_assign = None\n            self.left = None\n            self.right = None\n\n    def __init__(self, data):\n        if not data:\n            raise ValueError(\"Data cannot be empty\")\n        self.n = len(data)\n        self.root = self._build(data, 0, self.n)\n\n    def _build(self, data, l, r):\n        node = self.Node(l, r)\n        if r - l == 1:\n            node.sum = data[l]\n            node.max_subarray = data[l]\n            return node\n        mid = (l + r) // 2\n        node.left = self._build(data, l, mid)\n        node.right = self._build(data, mid, r)\n        self._pull(node)\n        return node\n\n    def _pull(self, node):\n        left = node.left\n        right = node.right\n        node.sum = left.sum + right.sum\n        node.max_subarray = max(left.max_subarray, right.max_subarray, left.sum + right.max_subarray)\n\n    def _apply_assign(self, node, v):\n        node.sum = v * (node.r - node.l)\n        node.max_subarray = v\n        node.lazy_assign = v\n\n    def _push(self, node):\n        if node.lazy_assign is not None:\n            self._apply_assign(node.left, node.lazy_assign)\n            self._apply_assign(node.right, node.lazy_assign)\n            node.lazy_assign = None\n\n    def _assign(self, node, l, r, v):\n        if node.r <= l or node.l >= r:\n            return\n        if l <= node.l and node.r <= r:\n            self._apply_assign(node, v)\n            return\n        self._push(node)\n        self._assign(node.left, l, r, v)\n        self._assign(node.right, l, r, v)\n        self._pull(node)\n\n    def _query_sum(self, node, l, r):\n        if node.r <= l or node.l >= r:\n            return 0\n        if l <= node.l and node.r <= r:\n            return node.sum\n        self._push(node)\n        return self._query_sum(node.left, l, r) + self._query_sum(node.right, l, r)\n\n    def _query_max_subarray(self, node, l, r):\n        if node.r <= l or node.l >= r:\n            return float('-inf')\n        if l <= node.l and node.r <= r:\n            return node.max_subarray\n        self._push(node)\n        left_max = self._query_max_subarray(node.left, l, r)\n        right_max = self._query_max_subarray(node.right, l, r)\n        mid_max = self._query_sum(node.left, l, r) + right_max\n        return max(left_max, right_max, mid_max)\n\n    def assign(self, l, r, v):\n        if not (0 <= l < r <= self.n):\n            raise IndexError(\"Invalid range\")\n        self._assign(self.root, l, r, v)\n\n    def sum(self, l, r):\n        if not (0 <= l < r <= self.n):\n            raise IndexError(\"Invalid range\")\n        return self._query_sum(self.root, l, r)\n\n    def max_subarray(self, l, r):\n        if not (0 <= l < r <= self.n):\n            raise IndexError(\"Invalid range\")\n        return self._query_max_subarray(self.root, l, r)\n```",
    "passed": 5,
    "test_error": "    +  and   3482 = _kadane([1, -2, -25, 26, -28, -21, ...])\n\ntest_range_array.py:185: AssertionError\n_________________ test_large_performance_and_spot_correctness __________________\n\n    def test_large_performance_and_spot_correctness():\n        rng = 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                if k % 200 == 0:          # spot check (O(n) each, sampled)\n                    assert got == sum(mirror[l:r])\n                    checks += 1\n            else:\n                got = ra.max_subarray(l, r)\n                if k % 200 == 0:\n>                   assert got == _kadane(mirror[l:r])\nE                   assert 48485 == 60686\nE                    +  where 60686 = _kadane([-3, -3, -3, -3, -3, -3, ...])\n\ntest_range_array.py:221: AssertionError\n=========================== short test summary info ============================\nFAILED test_range_array.py::test_worked_example_sum_and_max_subarray - assert...\nFAILED test_range_array.py::test_assign_updates_both_queries - assert 2 == 10\nFAILED test_range_array.py::test_assign_positive_then_negative_block - assert...\nFAILED test_range_array.py::test_partial_query_crossing_lazy_boundaries - ass...\nFAILED test_range_array.py::test_random_small_against_brute[0] - assert 14 == 15\nFAILED test_range_array.py::test_random_small_against_brute[1] - assert 3 == 9\nFAILED test_range_array.py::test_random_small_against_brute[2] - assert 13 == 27\nFAILED test_range_array.py::test_random_small_against_brute[3] - assert 6 == 8\nFAILED test_range_array.py::test_random_small_against_brute[4] - assert 13 == 17\nFAILED test_range_array.py::test_random_medium_against_brute[10] - assert 123...\nFAILED test_range_array.py::test_random_medium_against_brute[11] - assert 775...\nFAILED test_range_array.py::test_full_range_max_matches_kadane_after_updates\nFAILED test_range_array.py::test_large_performance_and_spot_correctness - ass...\n13 failed, 5 passed in 0.08s"
  },
  {
    "total": 18,
    "answer": "```python\nclass RangeArray:\n    class Node:\n        __slots__ = ('l', 'r', 'sum', 'max_subarray', 'lazy_assign', 'left', 'right')\n        def __init__(self, l, r):\n            self.l = l\n            self.r = r\n            self.sum = 0\n            self.max_subarray = float('-inf')\n            self.lazy_assign = None\n            self.left = None\n            self.right = None\n\n    def __init__(self, data):\n        if not data:\n            raise ValueError(\"Data cannot be empty\")\n        self.n = len(data)\n        self.root = self._build(data, 0, self.n)\n\n    def _build(self, data, l, r):\n        node = self.Node(l, r)\n        if r - l == 1:\n            node.sum = data[l]\n            node.max_subarray = data[l]\n            return node\n        mid = (l + r) // 2\n        node.left = self._build(data, l, mid)\n        node.right = self._build(data, mid, r)\n        self._pull(node)\n        return node\n\n    def _pull(self, node):\n        left = node.left\n        right = node.right\n        node.sum = left.sum + right.sum\n        node.max_subarray = max(left.max_subarray, right.max_subarray, left.sum + right.max_subarray)\n\n    def _apply_assign(self, node, v):\n        node.sum = v * (node.r - node.l)\n        node.max_subarray = v\n        node.lazy_assign = v\n\n    def _push(self, node):\n        if node.lazy_assign is not None:\n            self._apply_assign(node.left, node.lazy_assign)\n            self._apply_assign(node.right, node.lazy_assign)\n            node.lazy_assign = None\n\n    def _assign(self, node, l, r, v):\n        if node.r <= l or node.l >= r:\n            return\n        if l <= node.l and node.r <= r:\n            self._apply_assign(node, v)\n            return\n        self._push(node)\n        self._assign(node.left, l, r, v)\n        self._assign(node.right, l, r, v)\n        self._pull(node)\n\n    def _query_sum(self, node, l, r):\n        if node.r <= l or node.l >= r:\n            return 0\n        if l <= node.l and node.r <= r:\n            return node.sum\n        self._push(node)\n        return self._query_sum(node.left, l, r) + self._query_sum(node.right, l, r)\n\n    def _query_max_subarray(self, node, l, r):\n        if node.r <= l or node.l >= r:\n            return float('-inf')\n        if l <= node.l and node.r <= r:\n            return node.max_subarray\n        self._push(node)\n        left_max = self._query_max_subarray(node.left, l, r)\n        right_max = self._query_max_subarray(node.right, l, r)\n        mid_max = self._query_sum(node.left, l, r) + right_max\n        return max(left_max, right_max, mid_max)\n\n    def assign(self, l, r, v):\n        if not (0 <= l < r <= self.n):\n            raise IndexError(\"Invalid range\")\n        self._assign(self.root, l, r, v)\n\n    def sum(self, l, r):\n        if not (0 <= l < r <= self.n):\n            raise IndexError(\"Invalid range\")\n        return self._query_sum(self.root, l, r)\n\n    def max_subarray(self, l, r):\n        if not (0 <= l < r <= self.n):\n            raise IndexError(\"Invalid range\")\n        return self._query_max_subarray(self.root, l, r)\n```",
    "passed": 5,
    "test_error": ""
  }
]