cp_library_rs/data_structure/
acc2d.rs

1//! 2次元累積和
2
3use num_traits::Num;
4
5/// acc2D
6/// - 2次元累積和を取る
7///
8/// **戻り値**
9/// - `|r_start, r_end, c_start, c_end|: (usize, usize, usize, usize) -> T`
10#[allow(clippy::ptr_arg)]
11pub fn acc2D<T: Num + Copy>(array: &Vec<Vec<T>>) -> impl Fn(usize, usize, usize, usize) -> T {
12    let (H, W) = (array.len(), array[0].len());
13    let mut S = vec![vec![T::zero(); W + 1]; H + 1];
14    for i in 0..H {
15        for j in 0..W {
16            S[i + 1][j + 1] = array[i][j] + S[i][j + 1] + S[i + 1][j] - S[i][j];
17        }
18    }
19    move |r_start: usize, r_end: usize, c_start: usize, c_end: usize| -> T {
20        S[r_end][c_end] + S[r_start][c_start] - S[r_end][c_start] - S[r_start][c_end]
21    }
22}