Minimum sum of values by dividing array

impl Solution {
  // Build sparse table for range minimum queries
  fn build_spt(arr: &[i32]) -> Vec<Vec<i32>> {
    let n = arr.len();
    if n == 0 {
      return vec![];
    }
    let log = (usize::BITS - n.leading_zeros()) as usize; // ceil(log2(n)) + 1
    let mut spt = vec![arr.to_vec()];
    for k in 1..=log {
      let half = 1 << (k - 1);
      if half >= n {
        break;
      }
      let prev = spt.last().unwrap().clone();
      let cur: Vec<i32> = (0..n)
        .map(|i| {
          let j = i + half;
          if j < n { prev[i].min(prev[j]) } else { prev[i] }
        })
        .collect();
      spt.push(cur);
    }
    spt
  }

  fn query_spt(spt: &[Vec<i32>], l: usize, r: usize) -> i32 {
    if l > r || spt.is_empty() {
      return i32::MAX / 2;
    }
    let len = r - l + 1;
    let k = (usize::BITS - len.leading_zeros() - 1) as usize;
    if k >= spt.len() {
      return *spt.last().unwrap()[l..=r].iter().min().unwrap_or(&(i32::MAX / 2));
    }
    spt[k][l].min(spt[k][r + 1 - (1 << k)])
  }

  pub fn minimum_value_sum(nums: Vec<i32>, and_values: Vec<i32>) -> i32 {
    let n = nums.len();
    let m = and_values.len();
    const INF: i32 = i32::MAX / 2;

    // prev_dp[s] = min sum for previous segments where coverage ends before index s
    // prev_dp[0] = 0 (no segments, coverage starts at 0)
    let mut prev_dp = vec![INF; n + 1];
    prev_dp[0] = 0;

    for j in 0..m {
      let mut curr_dp = vec![INF; n + 1];
      let target = and_values[j];

      // Build range min sparse table on prev_dp[0..n]
      let spt = Self::build_spt(&prev_dp[..n]);

      // groups: (and_val, start_index) representing that if current segment starts at s
      // in [start_index, next_group.start_index - 1], AND(nums[s..=i]) == and_val
      let mut groups: Vec<(i32, usize)> = Vec::new();

      for i in 0..n {
        // AND all existing groups with nums[i]
        for g in groups.iter_mut() {
          g.0 &= nums[i];
        }
        // Add new group: segment starting at i has AND = nums[i]
        groups.push((nums[i], i));
        // Deduplicate consecutive equal and_vals, keeping leftmost start
        {
          let mut write = 0usize;
          for read in 0..groups.len() {
            if write == 0 || groups[write - 1].0 != groups[read].0 {
              groups[write] = groups[read];
              write += 1;
            }
            // else: same val, skip (keep the first/leftmost one at write-1)
          }
          groups.truncate(write);
        }

        // Find group where and_val == target using binary search
        // groups are sorted by start index (ascending), and_vals are non-decreasing
        if let Ok(g) = groups.binary_search_by_key(&target, |g| g.0) {
          // Note: binary_search may not find the first occurrence if duplicates exist,
          // but after dedup there are no duplicates, so this is fine.
          let s_start = groups[g].1;
          let s_end = if g + 1 < groups.len() {
            groups[g + 1].1 - 1
          } else {
            i
          };
          let min_prev = Self::query_spt(&spt, s_start, s_end);
          if min_prev < INF {
            let new_val = min_prev.saturating_add(nums[i]);
            if new_val < curr_dp[i + 1] {
              curr_dp[i + 1] = new_val;
            }
          }
        }
      }

      prev_dp = curr_dp;
    }

    let ans = prev_dp[n];
    if ans >= INF { -1 } else { ans }
  }
}