array_range_query/
lib.rs

1//! High-performance segment trees and lazy segment trees for efficient range queries and updates.
2//!
3//! //! array_range_query: See full docs at <https://docs.rs/array_range_query> or in [README.md](../README.md)
4//!
5//! This library provides generic implementations of segment trees that work with any
6//! associative operation, plus specialized helper types for common operations like sum, min, and max.
7//!
8//! # Quick Start
9//!
10//! ```rust
11//! use array_range_query::{SegTreeSum, LazySegTreeAddSum};
12//!
13//! // Segment tree for range sum queries
14//! let mut tree = SegTreeSum::<i32>::from_vec(vec![1, 2, 3, 4, 5]);
15//! assert_eq!(tree.query(1..4), 9); // sum of [2, 3, 4]
16//! tree.update(2, 10);
17//! assert_eq!(tree.query(..), 22);
18//!
19//! // Lazy segment tree for range add updates and sum queries
20//! let mut lazy_tree = LazySegTreeAddSum::<i32>::from_vec(vec![1, 2, 3, 4, 5]);
21//! lazy_tree.update(1..4, 10); // add 10 to range [1, 4)
22//! assert_eq!(lazy_tree.query(..), 45);
23//! ```
24
25pub(crate) mod utils;
26
27mod seg_tree_node;
28pub use seg_tree_node::SegTreeNode;
29
30mod seg_tree;
31pub use seg_tree::{SegTree, SegTreeSpec};
32
33mod lazy_seg_tree;
34pub use lazy_seg_tree::{LazySegTree, LazySegTreeSpec};
35
36pub mod helpers;
37pub use helpers::{LazySegTreeAddMax, LazySegTreeAddMin, LazySegTreeAddSum, LazySegTreeReplaceSum};
38pub use helpers::{SegTreeMax, SegTreeMin, SegTreeSum};
array_range_query/lib.rs

array_range_query/
lib.rs
