[Rust] 일반 세그먼트 트리
현재 핵심 구조체는 다음과 같습니다.
pub struct SegTree<T, F>
where
T: Clone + Copy,
F: Fn(T, T) -> T,
{
n: i32,
default: T,
cell: Vec<T>,
lazy: Vec<T>,
op: F,
}
그리고 사용법:
let mut tree = SegTree::new(10, i32::MIN, std::cmp::max);
tree.insert(1, 10);
tree.insert(2, 20);
assert_eq!(tree.query(1, 10), 20);
tree.insert_range(3, 6, 10);
assert_eq!(tree.query(5, 10), 10);
여기서 op는 세그먼트 트리가 수행하는 작업(최소, 최대, gcd 또는 사용자 정의)이고 default는 쿼리 기본값으로 반환되어야 하는 값이며 초기화 중에 저장됩니다.
주요 이점은 더 복잡한 segtree를 비교적 쉽게 작성할 수 있다는 것입니다.
예:
문제: https://codeforces.com/contest/1557/problem/D
내 솔루션(https://codeforces.com/contest/1557/submission/154901530)은 다음을 사용합니다.
let mut seg_tree = SegTree::new(
points.len(),
(0, 0),
|left: (usize, usize), right: (usize, usize)| if left.1 > right.1 { left } else { right },
);
누군가 필요할 경우를 대비하여 여기에서 full implementation을 공유합니다.
필요에 따라 계속 수정하겠습니다. 누군가 그것을 사용하기로 결정하고 버그를 찾거나 기능 요청이 있는 경우 알려주세요.
Reference
이 문제에 관하여([Rust] 일반 세그먼트 트리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/satylogin/rust-generic-segment-tree-3cng텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)