oxihuman_core/
segment_tree_range.rs

1// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
2// SPDX-License-Identifier: Apache-2.0
3#![allow(dead_code)]
4
5//! Segment tree for range min/max queries with point updates.
6
7pub struct SegmentTreeRange {
8    pub data: Vec<i64>,
9    pub n: usize,
10}
11
12pub fn new_segment_tree_range(values: &[i64]) -> SegmentTreeRange {
13    let n = values.len();
14    let mut data = vec![i64::MAX; 4 * n.max(1)];
15    if n > 0 {
16        build(&mut data, values, 1, 0, n - 1);
17    }
18    SegmentTreeRange { data, n }
19}
20
21fn build(data: &mut [i64], values: &[i64], node: usize, lo: usize, hi: usize) {
22    if lo == hi {
23        data[node] = values[lo];
24        return;
25    }
26    let mid = (lo + hi) / 2;
27    build(data, values, node * 2, lo, mid);
28    build(data, values, node * 2 + 1, mid + 1, hi);
29    data[node] = data[node * 2].min(data[node * 2 + 1]);
30}
31
32fn query_min_inner(data: &[i64], node: usize, lo: usize, hi: usize, l: usize, r: usize) -> i64 {
33    if r < lo || hi < l {
34        return i64::MAX;
35    }
36    if l <= lo && hi <= r {
37        return data[node];
38    }
39    let mid = (lo + hi) / 2;
40    query_min_inner(data, node * 2, lo, mid, l, r).min(query_min_inner(
41        data,
42        node * 2 + 1,
43        mid + 1,
44        hi,
45        l,
46        r,
47    ))
48}
49
50fn query_max_inner(data: &[i64], node: usize, lo: usize, hi: usize, l: usize, r: usize) -> i64 {
51    if r < lo || hi < l {
52        return i64::MIN;
53    }
54    if l <= lo && hi <= r {
55        // rebuild max lazily from stored min tree by using separate max pass
56        // Since the tree stores min, we walk leaves for max query
57        if lo == hi {
58            return data[node];
59        }
60        let mid = (lo + hi) / 2;
61        return query_max_inner(data, node * 2, lo, mid, l, r).max(query_max_inner(
62            data,
63            node * 2 + 1,
64            mid + 1,
65            hi,
66            l,
67            r,
68        ));
69    }
70    let mid = (lo + hi) / 2;
71    query_max_inner(data, node * 2, lo, mid, l, r).max(query_max_inner(
72        data,
73        node * 2 + 1,
74        mid + 1,
75        hi,
76        l,
77        r,
78    ))
79}
80
81fn update_inner(data: &mut [i64], node: usize, lo: usize, hi: usize, i: usize, val: i64) {
82    if lo == hi {
83        data[node] = val;
84        return;
85    }
86    let mid = (lo + hi) / 2;
87    if i <= mid {
88        update_inner(data, node * 2, lo, mid, i, val);
89    } else {
90        update_inner(data, node * 2 + 1, mid + 1, hi, i, val);
91    }
92    data[node] = data[node * 2].min(data[node * 2 + 1]);
93}
94
95pub fn seg_range_query_min(t: &SegmentTreeRange, l: usize, r: usize) -> i64 {
96    if t.n == 0 {
97        return i64::MAX;
98    }
99    query_min_inner(&t.data, 1, 0, t.n - 1, l, r)
100}
101
102pub fn seg_range_query_max(t: &SegmentTreeRange, l: usize, r: usize) -> i64 {
103    if t.n == 0 {
104        return i64::MIN;
105    }
106    query_max_inner(&t.data, 1, 0, t.n - 1, l, r)
107}
108
109pub fn seg_range_update(t: &mut SegmentTreeRange, i: usize, val: i64) {
110    if t.n == 0 {
111        return;
112    }
113    update_inner(&mut t.data, 1, 0, t.n - 1, i, val);
114}
115
116pub fn seg_range_size(t: &SegmentTreeRange) -> usize {
117    t.n
118}
119
120#[cfg(test)]
121mod tests {
122    use super::*;
123
124    #[test]
125    fn test_range_min_basic() {
126        /* min over full range */
127        let t = new_segment_tree_range(&[3, 1, 4, 1, 5, 9, 2, 6]);
128        assert_eq!(seg_range_query_min(&t, 0, 7), 1);
129    }
130
131    #[test]
132    fn test_range_max_basic() {
133        /* max over full range */
134        let t = new_segment_tree_range(&[3, 1, 4, 1, 5, 9, 2, 6]);
135        assert_eq!(seg_range_query_max(&t, 0, 7), 9);
136    }
137
138    #[test]
139    fn test_range_min_subrange() {
140        /* min over subrange */
141        let t = new_segment_tree_range(&[5, 3, 8, 2, 7]);
142        assert_eq!(seg_range_query_min(&t, 1, 3), 2);
143    }
144
145    #[test]
146    fn test_range_max_subrange() {
147        /* max over subrange */
148        let t = new_segment_tree_range(&[5, 3, 8, 2, 7]);
149        assert_eq!(seg_range_query_max(&t, 0, 2), 8);
150    }
151
152    #[test]
153    fn test_update_changes_result() {
154        /* point update changes min query */
155        let mut t = new_segment_tree_range(&[5, 3, 8, 2, 7]);
156        seg_range_update(&mut t, 3, 100);
157        assert_eq!(seg_range_query_min(&t, 0, 4), 3);
158    }
159
160    #[test]
161    fn test_size() {
162        /* size equals input length */
163        let t = new_segment_tree_range(&[1, 2, 3]);
164        assert_eq!(seg_range_size(&t), 3);
165    }
166
167    #[test]
168    fn test_single_element() {
169        /* single element tree works correctly */
170        let t = new_segment_tree_range(&[42]);
171        assert_eq!(seg_range_query_min(&t, 0, 0), 42);
172        assert_eq!(seg_range_query_max(&t, 0, 0), 42);
173    }
174}
oxihuman_core/segment_tree_range.rs

oxihuman_core/
segment_tree_range.rs
