import%20marimo%0A%0A__generated_with%20%3D%20%220.24.0%22%0Aapp%20%3D%20marimo.App()%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Algebra%20Behind%20Prefix%20Sum%3A%201D%20and%202D%0A%0A%20%20%20%20%23%23%201D%20Prefix%20Sum%0A%20%20%20%201D%20prefix%20sum%20is%20a%20technique%20used%20to%20compute%20cumulative%20sums%20efficiently.%20Given%20an%20array%20%60A%60%20of%20size%20%60n%60%2C%20the%20prefix%20sum%20array%20%60P%60%20is%20defined%20as%3A%0A%20%20%20%20%24%24%0A%20%20%20%20P%5Bi%5D%20%3D%20A%5B0%5D%20%2B%20A%5B1%5D%20%2B%20%5Cdots%20%2B%20A%5Bi%5D%0A%20%20%20%20%24%24%0A%20%20%20%20for%20%24%200%20%5Cleq%20i%20%3C%20n%20%24.%0A%0A%20%20%20%20%23%23%23%20Recursive%20Relation%0A%20%20%20%20%24%24%0A%20%20%20%20P%5Bi%5D%20%3D%20P%5Bi-1%5D%20%2B%20A%5Bi%5D%2C%20%5Cquad%20%5Ctext%7Bfor%20%7D%20i%20%3E%200%0A%20%20%20%20%24%24%0A%20%20%20%20with%20the%20base%20case%3A%0A%20%20%20%20%24%24%0A%20%20%20%20P%5B0%5D%20%3D%20A%5B0%5D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20%23%23%23%20Usage%0A%20%20%20%20To%20compute%20the%20sum%20of%20any%20subarray%20%24%20A%5Bl%3Ar%5D%20%24%20(inclusive)%3A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Ctext%7BSum%7D(A%5Bl%3Ar%5D)%20%3D%20P%5Br%5D%20-%20P%5Bl-1%5D%2C%20%5Cquad%20%5Ctext%7Bfor%20%7D%20l%20%3E%200%0A%20%20%20%20%24%24%0A%20%20%20%20If%20%24%20l%20%3D%200%20%24%3A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Ctext%7BSum%7D(A%5B0%3Ar%5D)%20%3D%20P%5Br%5D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%202D%20Prefix%20Sum%0A%20%20%20%202D%20prefix%20sum%20extends%20this%20concept%20to%20matrices.%20Given%20a%20matrix%20%60M%60%20of%20size%20%24%20n%20%5Ctimes%20m%20%24%2C%20the%202D%20prefix%20sum%20matrix%20%60P%60%20is%20defined%20as%3A%0A%20%20%20%20%24%24%0A%20%20%20%20P%5Bi%5D%5Bj%5D%20%3D%20%5Csum_%7B0%20%5Cleq%20x%20%5Cleq%20i%2C%200%20%5Cleq%20y%20%5Cleq%20j%7D%20M%5Bx%5D%5By%5D%0A%20%20%20%20%24%24%0A%20%20%20%20for%20%24%200%20%5Cleq%20i%20%3C%20n%20%24%2C%20%24%200%20%5Cleq%20j%20%3C%20m%20%24.%0A%0A%20%20%20%20%23%23%23%20Recursive%20Relation%0A%20%20%20%20%24%24%0A%20%20%20%20P%5Bi%5D%5Bj%5D%20%3D%20M%5Bi%5D%5Bj%5D%20%2B%20P%5Bi-1%5D%5Bj%5D%20%2B%20P%5Bi%5D%5Bj-1%5D%20-%20P%5Bi-1%5D%5Bj-1%5D%2C%20%5Cquad%20%5Ctext%7Bfor%20%7D%20i%2C%20j%20%3E%200%0A%20%20%20%20%24%24%0A%20%20%20%20with%20base%20cases%3A%0A%20%20%20%20%24%24%0A%20%20%20%20P%5Bi%5D%5B0%5D%20%3D%20%5Csum_%7Bx%3D0%7D%5Ei%20M%5Bx%5D%5B0%5D%2C%20%5Cquad%20P%5B0%5D%5Bj%5D%20%3D%20%5Csum_%7By%3D0%7D%5Ej%20M%5B0%5D%5By%5D%2C%20%5Cquad%20P%5B0%5D%5B0%5D%20%3D%20M%5B0%5D%5B0%5D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20%23%23%23%20Usage%0A%20%20%20%20To%20compute%20the%20sum%20of%20any%20submatrix%20%24%20M%5Bx1%3Ax2%5D%5By1%3Ay2%5D%20%24%3A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Ctext%7BSum%7D(M%5Bx1%3Ax2%5D%5By1%3Ay2%5D)%20%3D%20P%5Bx2%5D%5By2%5D%20-%20P%5Bx1-1%5D%5By2%5D%20-%20P%5Bx2%5D%5By1-1%5D%20%2B%20P%5Bx1-1%5D%5By1-1%5D%0A%20%20%20%20%24%24%0A%20%20%20%20Where%20adjustments%20are%20made%20based%20on%20boundary%20conditions%3A%0A%20%20%20%20-%20If%20%24%20x1%20%3D%200%20%24%2C%20omit%20%24%20P%5Bx1-1%5D%5By2%5D%20%24.%0A%20%20%20%20-%20If%20%24%20y1%20%3D%200%20%24%2C%20omit%20%24%20P%5Bx2%5D%5By1-1%5D%20%24.%0A%20%20%20%20-%20If%20both%20%24%20x1%20%3D%200%20%24%20and%20%24%20y1%20%3D%200%20%24%2C%20sum%20equals%20%24%20P%5Bx2%5D%5By2%5D%20%24.%0A%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%20Key%20Insights%0A%20%20%20%201.%20**Time%20Complexity**%3A%0A%20%20%20%20%20%20%20-%20Constructing%20the%20prefix%20sum%20array%2Fmatrix%3A%20%24%20O(n)%20%24%20for%201D%2C%20%24%20O(n%20%5Ctimes%20m)%20%24%20for%202D.%0A%20%20%20%20%20%20%20-%20Querying%20the%20sum%3A%20%24%20O(1)%20%24.%0A%0A%20%20%20%202.%20**Avoiding%20Double%20Counting**%3A%0A%20%20%20%20%20%20%20-%20In%20the%202D%20prefix%20sum%20formula%2C%20subtracting%20%24%20P%5Bi-1%5D%5Bj%5D%20%24%20and%20%24%20P%5Bi%5D%5Bj-1%5D%20%24%20removes%20extra%20sums%2C%20and%20adding%20back%20%24%20P%5Bi-1%5D%5Bj-1%5D%20%24%20corrects%20for%20over-subtraction.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20from%20typing%20import%20List%2C%20Tuple%0A%0A%20%20%20%20class%20PrefixSum1D%3A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20nums%3A%20List%5Bint%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20Initializes%20the%20prefix%20sum%20for%20a%201D%20array.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20Args%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20nums%20(List%5Bint%5D)%3A%20The%20input%20array%20of%20integers.%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20self.prefix%20%3D%20self._compute_prefix_sum(nums)%0A%0A%20%20%20%20%20%20%20%20%40staticmethod%0A%20%20%20%20%20%20%20%20def%20_compute_prefix_sum(nums%3A%20List%5Bint%5D)%20-%3E%20List%5Bint%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20Computes%20the%20prefix%20sum%20for%20the%20input%20array.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20Args%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20nums%20(List%5Bint%5D)%3A%20The%20input%20array%20of%20integers.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20Returns%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20List%5Bint%5D%3A%20The%20prefix%20sum%20array.%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20prefix%20%3D%20%5B0%5D%20*%20len(nums)%0A%20%20%20%20%20%20%20%20%20%20%20%20prefix%5B0%5D%20%3D%20nums%5B0%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20i%20in%20range(1%2C%20len(nums))%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20prefix%5Bi%5D%20%3D%20prefix%5Bi%20-%201%5D%20%2B%20nums%5Bi%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20prefix%0A%0A%20%20%20%20%20%20%20%20def%20range_sum(self%2C%20left%3A%20int%2C%20right%3A%20int)%20-%3E%20int%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20Calculates%20the%20sum%20of%20elements%20in%20the%20range%20%5Bleft%2C%20right%5D%20(inclusive).%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20Args%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20left%20(int)%3A%20Starting%20index%20of%20the%20range.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20right%20(int)%3A%20Ending%20index%20of%20the%20range.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20Returns%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%3A%20Sum%20of%20elements%20in%20the%20specified%20range.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20Raises%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ValueError%3A%20If%20the%20range%20indices%20are%20invalid.%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20left%20%3C%200%20or%20right%20%3E%3D%20len(self.prefix)%20or%20left%20%3E%20right%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20raise%20ValueError(%22Invalid%20range%20indices.%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20self.prefix%5Bright%5D%20-%20(self.prefix%5Bleft%20-%201%5D%20if%20left%20%3E%200%20else%200)%0A%0A%20%20%20%20%23%20Example%20for%201D%20Prefix%20Sum%0A%20%20%20%20nums%20%3D%20%5B1%2C%202%2C%203%2C%204%2C%205%5D%0A%20%20%20%20prefix_sum_1d%20%3D%20PrefixSum1D(nums)%0A%0A%20%20%20%20%23%20Range%20sum%20from%20index%201%20to%203%20(i.e.%2C%202%20%2B%203%20%2B%204)%0A%20%20%20%20print(f%22Range%20sum%20(1%20to%203)%3A%20%7Bprefix_sum_1d.range_sum(1%2C%203)%7D%22)%20%20%23%20Output%3A%209%0A%0A%20%20%20%20class%20PrefixSum2D%3A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20matrix%3A%20List%5BList%5Bint%5D%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20Initializes%20the%20prefix%20sum%20for%20a%202D%20matrix.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20Args%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20matrix%20(List%5BList%5Bint%5D%5D)%3A%20The%20input%202D%20matrix%20of%20integers.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20Raises%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ValueError%3A%20If%20the%20matrix%20is%20empty%20or%20contains%20empty%20rows.%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20not%20matrix%20or%20not%20matrix%5B0%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20raise%20ValueError(%22Input%20matrix%20must%20not%20be%20empty.%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20self.prefix%20%3D%20self._compute_prefix_sum_2d(matrix)%0A%0A%20%20%20%20%20%20%20%20%40staticmethod%0A%20%20%20%20%20%20%20%20def%20_compute_prefix_sum_2d(matrix%3A%20List%5BList%5Bint%5D%5D)%20-%3E%20List%5BList%5Bint%5D%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20Computes%20the%20prefix%20sum%20for%20the%20input%202D%20matrix.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20Args%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20matrix%20(List%5BList%5Bint%5D%5D)%3A%20The%20input%202D%20matrix%20of%20integers.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20Returns%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20List%5BList%5Bint%5D%5D%3A%20The%20prefix%20sum%202D%20matrix.%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20rows%2C%20cols%20%3D%20len(matrix)%2C%20len(matrix%5B0%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20prefix%20%3D%20%5B%5B0%5D%20*%20cols%20for%20_%20in%20range(rows)%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20i%20in%20range(rows)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20j%20in%20range(cols)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20prefix%5Bi%5D%5Bj%5D%20%3D%20matrix%5Bi%5D%5Bj%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20i%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20prefix%5Bi%5D%5Bj%5D%20%2B%3D%20prefix%5Bi%20-%201%5D%5Bj%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20j%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20prefix%5Bi%5D%5Bj%5D%20%2B%3D%20prefix%5Bi%5D%5Bj%20-%201%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20i%20%3E%200%20and%20j%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20prefix%5Bi%5D%5Bj%5D%20-%3D%20prefix%5Bi%20-%201%5D%5Bj%20-%201%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20prefix%0A%0A%20%20%20%20%20%20%20%20def%20range_sum(self%2C%20top_left%3A%20Tuple%5Bint%2C%20int%5D%2C%20bottom_right%3A%20Tuple%5Bint%2C%20int%5D)%20-%3E%20int%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20Calculates%20the%20sum%20of%20elements%20within%20the%20submatrix%20defined%20by%20the%20given%20corners.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20Args%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20top_left%20(Tuple%5Bint%2C%20int%5D)%3A%20(row%2C%20col)%20for%20the%20top-left%20corner%20of%20the%20submatrix.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20bottom_right%20(Tuple%5Bint%2C%20int%5D)%3A%20(row%2C%20col)%20for%20the%20bottom-right%20corner%20of%20the%20submatrix.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20Returns%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%3A%20Sum%20of%20elements%20in%20the%20specified%20submatrix.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20Raises%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ValueError%3A%20If%20the%20submatrix%20corners%20are%20invalid.%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20row1%2C%20col1%20%3D%20top_left%0A%20%20%20%20%20%20%20%20%20%20%20%20row2%2C%20col2%20%3D%20bottom_right%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20row1%20%3E%20row2%20or%20col1%20%3E%20col2%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20raise%20ValueError(%22Invalid%20submatrix%20corners.%22)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20total%20%3D%20self.prefix%5Brow2%5D%5Bcol2%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20col1%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20total%20-%3D%20self.prefix%5Brow2%5D%5Bcol1%20-%201%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20row1%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20total%20-%3D%20self.prefix%5Brow1%20-%201%5D%5Bcol2%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20row1%20%3E%200%20and%20col1%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20total%20%2B%3D%20self.prefix%5Brow1%20-%201%5D%5Bcol1%20-%201%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20total%0A%0A%20%20%20%20%23%20Example%20for%202D%20Prefix%20Sum%0A%20%20%20%20matrix%20%3D%20%5B%5B1%2C%202%2C%203%5D%2C%20%5B4%2C%205%2C%206%5D%2C%20%5B7%2C%208%2C%209%5D%5D%0A%20%20%20%20prefix_sum_2d%20%3D%20PrefixSum2D(matrix)%0A%0A%20%20%20%20%23%20Sum%20of%20submatrix%20from%20(0%2C%200)%20to%20(1%2C%201)%20(top-left%20to%20bottom-right%20corner)%0A%20%20%20%20print(f%22Range%20sum%20(top-left%20(0%2C0)%20to%20bottom-right%20(1%2C1))%3A%20%7Bprefix_sum_2d.range_sum((0%2C%200)%2C%20(1%2C%201))%7D%22)%20%20%23%20Output%3A%2012%0A%0A%20%20%20%20%23%20Sum%20of%20submatrix%20from%20(1%2C%201)%20to%20(2%2C%202)%0A%20%20%20%20print(f%22Range%20sum%20(top-left%20(1%2C1)%20to%20bottom-right%20(2%2C2))%3A%20%7Bprefix_sum_2d.range_sum((1%2C%201)%2C%20(2%2C%202))%7D%22)%20%20%23%20Output%3A%2028%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A
29cb66acb8865d702426f0900b957407