<p>You are given a <strong>0-indexed</strong> <code>m x n</code> integer matrix <code>grid</code>. Your initial position is at the <strong>top-left</strong> cell <code>(0, 0)</code>.</p>

<p>Starting from the cell <code>(i, j)</code>, you can move to one of the following cells:</p>

<ul>
	<li>Cells <code>(i, k)</code> with <code>j &lt; k &lt;= grid[i][j] + j</code> (rightward movement), or</li>
	<li>Cells <code>(k, j)</code> with <code>i &lt; k &lt;= grid[i][j] + i</code> (downward movement).</li>
</ul>

<p>Return <em>the minimum number of cells you need to visit to reach the <strong>bottom-right</strong> cell</em> <code>(m - 1, n - 1)</code>. If there is no valid path, return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/01/25/ex1.png" style="width: 271px; height: 171px;" />
<pre>
<strong>Input:</strong> grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> The image above shows one of the paths that visits exactly 4 cells.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/01/25/ex2.png" style="width: 271px; height: 171px;" />
<pre>
<strong>Input:</strong> grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]]
<strong>Output:</strong> 3
<strong>Explanation: </strong>The image above shows one of the paths that visits exactly 3 cells.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/01/26/ex3.png" style="width: 181px; height: 81px;" />
<pre>
<strong>Input:</strong> grid = [[2,1,0],[1,0,0]]
<strong>Output:</strong> -1
<strong>Explanation:</strong> It can be proven that no path exists.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= grid[i][j] &lt; m * n</code></li>
	<li><code>grid[m - 1][n - 1] == 0</code></li>
</ul>

class Solution:
  def minimumVisitedCells(self, grid: List[List[int]]) -> int:
    row_count = len(grid)
    col_count = len(grid[0])
    rows = [RangeArray(col_count) for _ in range(row_count)]
    cols = [RangeArray(row_count) for _ in range(col_count)]
    rows[0].update(0, 0, 1)
    for ri in range(row_count):
      for ci in range(col_count):
        min_cell_count = min(rows[ri].query(ci), cols[ci].query(ri))
        if grid[ri][ci] == 0:
          continue
        if ci + 1 < col_count:
          rows[ri].update(ci + 1, min(ci + grid[ri][ci], col_count - 1), min_cell_count + 1)
        if ri + 1 < row_count:
          cols[ci].update(ri + 1, min(ri + grid[ri][ci], row_count - 1), min_cell_count + 1)
    return min_cell_count if min_cell_count != math.inf else -1


import math


class RangeArray:

  def __init__(self, size: int):
    assert size > 0
    self._leaf_count = _get_required_leaf_count(size)
    self._node_count = self._leaf_count * 2  # including the sentinel 0th node
    self._values = [math.inf] * self._node_count

  def query(self, i: int):
    assert 0 <= i < self._leaf_count
    i += self._leaf_count
    return min(self._values[j] for j in _get_ancestors(i))

  def update(self, li: int, ri: int, value):
    assert 0 <= li <= ri < self._leaf_count
    li += self._leaf_count
    ri += self._leaf_count
    for j in _get_smallest_cover(li, ri):
      self._values[j] = min(self._values[j], value)


def _get_required_leaf_count(size: int):
  """Calculates the required number of leaf nodes for a segment tree.

  Segment trees require a complete binary tree structure, hence the number of
  leaf nodes needed to accommodate elements with indices in the range [0, size) 
  needs to be the smallest power of 2 greater than or equal to 'size'.
  """
  msb = 1 << (size.bit_length() - 1)
  return msb * 2 if msb < size else msb


def _get_smallest_cover(i: int, j: int):
  """Finds the smallest set of segments that cover the given range.

  Computes the smallest set of segments (represented by nodes) in a segment
  tree that completely covers the range between nodes i and j (inclusive).
  Each node in the resulting list represents a segment that lies entirely
  within the given range. Nodes in the list are arranged from left to right. 

  The list includes:
    - Right children of nodes on the path from leaf node i to the LCA(i, j).
    - Left children of nodes on the path from the LCA(i, j) to leaf node j.
  """
  # assert 0 < i <= j and i.bit_length() == j.bit_length()
  ans = []
  left_children = []
  while i <= j:
    if i % 2 == 1:
      ans.append(i)
      i += 1
    if j % 2 == 0:
      left_children.append(j)
      j -= 1
    i //= 2
    j //= 2
  ans.extend(reversed(left_children))
  return ans


def _get_ancestors(i: int, j: int = None):
  """Finds the list ancestors of given nodes in a segment tree.

  If only one node 'i' is provided, the list of ancestors includes 'i' itself.
  If two node indices 'i' and 'j' are provided, the list contains all their
  ancestors, with common ancestors appearing only once (not duplicated).
  Nodes in the list are arranged in a bottom-up order.
  """
  if j is None:
    ans = [i]
    j = i
  else:
    ans = []
  # assert 0 < i <= j
  i //= 2
  j //= 2
  while i != j:
    if i > j:
      ans.append(i)
      i //= 2
    else:
      ans.append(j)
      j //= 2
  while i > 0:
    ans.append(i)
    i //= 2
  return ans
7097