oxihuman-core 0.1.2

Core data structures, algorithms, and asset management for OxiHuman
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
// SPDX-License-Identifier: Apache-2.0
#![allow(dead_code)]

//! 2D prefix sum table for O(1) rectangular range queries.

pub struct PrefixSum2d {
    pub data: Vec<i64>,
    pub rows: usize,
    pub cols: usize,
}

pub fn new_prefix_sum_2d(grid: &[Vec<i64>]) -> PrefixSum2d {
    let rows = grid.len();
    let cols = if rows > 0 { grid[0].len() } else { 0 };
    // data[i][j] = prefix sum of rectangle [0..i][0..j] (1-indexed)
    let mut data = vec![0i64; (rows + 1) * (cols + 1)];
    let idx = |r: usize, c: usize| r * (cols + 1) + c;
    for r in 1..=rows {
        for c in 1..=cols {
            let v = grid[r - 1].get(c - 1).copied().unwrap_or(0);
            data[idx(r, c)] =
                v + data[idx(r - 1, c)] + data[idx(r, c - 1)] - data[idx(r - 1, c - 1)];
        }
    }
    PrefixSum2d { data, rows, cols }
}

pub fn ps2d_query(t: &PrefixSum2d, r1: usize, c1: usize, r2: usize, c2: usize) -> i64 {
    if t.rows == 0 || t.cols == 0 {
        return 0;
    }
    let cols1 = t.cols + 1;
    let idx = |r: usize, c: usize| r * cols1 + c;
    t.data[idx(r2 + 1, c2 + 1)] - t.data[idx(r1, c2 + 1)] - t.data[idx(r2 + 1, c1)]
        + t.data[idx(r1, c1)]
}

pub fn ps2d_rows(t: &PrefixSum2d) -> usize {
    t.rows
}

pub fn ps2d_cols(t: &PrefixSum2d) -> usize {
    t.cols
}

#[cfg(test)]
mod tests {
    use super::*;

    fn make_grid() -> Vec<Vec<i64>> {
        vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]]
    }

    #[test]
    fn test_full_sum() {
        /* sum of full grid is 45 */
        let t = new_prefix_sum_2d(&make_grid());
        assert_eq!(ps2d_query(&t, 0, 0, 2, 2), 45);
    }

    #[test]
    fn test_single_cell() {
        /* single cell query returns that cell's value */
        let t = new_prefix_sum_2d(&make_grid());
        assert_eq!(ps2d_query(&t, 1, 1, 1, 1), 5);
    }

    #[test]
    fn test_subgrid() {
        /* 2x2 subgrid sum */
        let t = new_prefix_sum_2d(&make_grid());
        assert_eq!(ps2d_query(&t, 0, 0, 1, 1), 12);
    }

    #[test]
    fn test_rows_cols() {
        /* rows and cols match input dimensions */
        let t = new_prefix_sum_2d(&make_grid());
        assert_eq!(ps2d_rows(&t), 3);
        assert_eq!(ps2d_cols(&t), 3);
    }

    #[test]
    fn test_single_row() {
        /* single row grid works correctly */
        let grid = vec![vec![1i64, 2, 3, 4]];
        let t = new_prefix_sum_2d(&grid);
        assert_eq!(ps2d_query(&t, 0, 1, 0, 2), 5);
    }

    #[test]
    fn test_empty_grid() {
        /* empty grid returns 0 */
        let t = new_prefix_sum_2d(&[]);
        assert_eq!(ps2d_rows(&t), 0);
        assert_eq!(ps2d_cols(&t), 0);
    }
}