import re
regex = re.compile(r"\\\[(.*?)\\\]", flags=re.MULTILINE | re.DOTALL)
test_str = ("Here's the explanation of prefix sum variations along with their corresponding Python code:\n\n"
"### 1. **Basic Prefix Sum (1D Array)**\n"
" - **Description**: This is the most common variation where you compute a running total of an array. The prefix sum at index `i` is the sum of all elements from index `0` to `i`.\n"
" - **Use Case**: Range sum queries in constant time.\n"
" - **Formula**: \n"
" \\[\n"
" \\text{prefix}[i] = \\text{prefix}[i-1] + \\text{arr}[i]\n"
" \\]\n"
" - **Query**: To get the sum of elements between two indices `l` and `r`, the formula becomes:\n"
" \\[\n"
" \\text{sum}(l, r) = \\text{prefix}[r] - \\text{prefix}[l-1]\n"
" \\]\n\n"
" **Python Code**:\n\n"
" ```python\n"
" def prefix_sum(arr):\n"
" prefix = [0] * len(arr)\n"
" prefix[0] = arr[0]\n"
" for i in range(1, len(arr)):\n"
" prefix[i] = prefix[i - 1] + arr[i]\n"
" return prefix\n\n"
" def range_sum(prefix, l, r):\n"
" if l == 0:\n"
" return prefix[r]\n"
" return prefix[r] - prefix[l - 1]\n\n"
" # Example usage:\n"
" arr = [1, 2, 3, 4, 5]\n"
" prefix = prefix_sum(arr)\n"
" result = range_sum(prefix, 1, 3) # Sum of arr[1] to arr[3] -> 2+3+4 = 9\n"
" print(result)\n"
" ```\n\n"
"### 2. **2D Prefix Sum (Matrix)**\n"
" - **Description**: This variation extends the prefix sum to two dimensions, commonly used for range queries in a 2D matrix.\n"
" - **Use Case**: Efficiently calculate the sum of elements in any rectangular submatrix.\n"
" - **Formula**: \n"
" $$[\n"
" \\text{prefix}[i][j] = \\text{arr}[i][j] + \\text{prefix}[i-1][j] + \\text{prefix}[i][j-1] - \\text{prefix}[i-1][j-1]\n"
" ]$$\n"
" - **Query**: To get the sum of a submatrix from `(r1, c1)` to `(r2, c2)`, use:\n"
" \\[\n"
" \\text{sum}(r1, c1, r2, c2) = \\text{prefix}[r2][c2] - \\text{prefix}[r1-1][c2] - \\text{prefix}[r2][c1-1] + \\text{prefix}[r1-1][c1-1]\n"
" \\]\n\n"
" **Python Code**:\n\n"
" ```python\n"
" def prefix_sum_2d(matrix):\n"
" rows, cols = len(matrix), len(matrix[0])\n"
" prefix = [[0] * cols for _ in range(rows)]\n"
" prefix[0][0] = matrix[0][0]\n"
" \n"
" # First row\n"
" for j in range(1, cols):\n"
" prefix[0][j] = prefix[0][j - 1] + matrix[0][j]\n"
" \n"
" # First column\n"
" for i in range(1, rows):\n"
" prefix[i][0] = prefix[i - 1][0] + matrix[i][0]\n"
" \n"
" # Rest of the matrix\n"
" for i in range(1, rows):\n"
" for j in range(1, cols):\n"
" prefix[i][j] = matrix[i][j] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1]\n"
" \n"
" return prefix\n\n"
" def range_sum_2d(prefix, r1, c1, r2, c2):\n"
" total = prefix[r2][c2]\n"
" if r1 > 0:\n"
" total -= prefix[r1 - 1][c2]\n"
" if c1 > 0:\n"
" total -= prefix[r2][c1 - 1]\n"
" if r1 > 0 and c1 > 0:\n"
" total += prefix[r1 - 1][c1 - 1]\n"
" return total\n\n"
" # Example usage:\n"
" matrix = [\n"
" [1, 2, 3],\n"
" [4, 5, 6],\n"
" [7, 8, 9]\n"
" ]\n"
" prefix = prefix_sum_2d(matrix)\n"
" result = range_sum_2d(prefix, 1, 1, 2, 2) # Sum of submatrix from (1, 1) to (2, 2) -> 5+6+8+9 = 28\n"
" print(result)\n"
" ```\n\n"
"### 3. **Prefix XOR (1D Array)**\n"
" - **Description**: Instead of summing elements, this variation computes the prefix XOR.\n"
" - **Use Case**: Useful for solving XOR-related problems efficiently, like range XOR queries.\n"
" - **Formula**: \n"
" \\[\n"
" \\text{prefix\\_xor}[i] = \\text{prefix\\_xor}[i-1] \\oplus \\text{arr}[i]\n"
" \\]\n"
" - **Query**: To get the XOR of elements between two indices `l` and `r`, the formula becomes:\n"
" \\[\n"
" \\text{xor}(l, r) = \\text{prefix\\_xor}[r] \\oplus \\text{prefix\\_xor}[l-1]\n"
" \\]\n\n"
" **Python Code**:\n\n"
" ```python\n"
" def prefix_xor(arr):\n"
" prefix = [0] * len(arr)\n"
" prefix[0] = arr[0]\n"
" for i in range(1, len(arr)):\n"
" prefix[i] = prefix[i - 1] ^ arr[i]\n"
" return prefix\n\n"
" def range_xor(prefix, l, r):\n"
" if l == 0:\n"
" return prefix[r]\n"
" return prefix[r] ^ prefix[l - 1]\n\n"
" # Example usage:\n"
" arr = [1, 2, 3, 4, 5]\n"
" prefix = prefix_xor(arr)\n"
" result = range_xor(prefix, 1, 3) # XOR of arr[1] to arr[3] -> 2 ^ 3 ^ 4 = 5\n"
" print(result)\n"
" ```\n\n"
"### 4. **Prefix Product (1D Array)**\n"
" - **Description**: Computes the running product of elements in an array.\n"
" - **Use Case**: Useful when handling multiplicative operations over ranges.\n"
" - **Formula**: \n"
" \\[\n"
" \\text{prefix}[i] = \\text{prefix}[i-1] \\times \\text{arr}[i]\n"
" \\]\n"
" - **Query**: To get the product of elements between two indices `l` and `r`, the formula becomes:\n"
" \\[\n"
" \\text{product}(l, r) = \\frac{\\text{prefix}[r]}{\\text{prefix}[l-1]}\n"
" \\]\n\n"
" **Python Code**:\n\n"
" ```python\n"
" def prefix_product(arr):\n"
" prefix = [1] * len(arr)\n"
" prefix[0] = arr[0]\n"
" for i in range(1, len(arr)):\n"
" prefix[i] = prefix[i - 1] * arr[i]\n"
" return prefix\n\n"
" def range_product(prefix, l, r):\n"
" if l == 0:\n"
" return prefix[r]\n"
" return prefix[r] // prefix[l - 1]\n\n"
" # Example usage:\n"
" arr = [1, 2, 3, 4, 5]\n"
" prefix = prefix_product(arr)\n"
" result = range_product(prefix, 1, 3) # Product of arr[1] to arr[3] -> 2*3*4 = 24\n"
" print(result)\n"
" ```\n\n"
"Each variation of the prefix sum adapts the basic idea to different mathematical operations like summing, XORing, or multiplying, providing efficient ways to handle range queries for different types of problems.")
subst = "$$\\1$$"
result = regex.sub(subst, test_str)
if result:
print(result)
Please keep in mind that these code samples are automatically generated and are not guaranteed to work. If you find any syntax errors, feel free to submit a bug report. For a full regex reference for Python, please visit: https://docs.python.org/3/library/re.html