A collection of useful data structures and algorithms
implementations:
monotone queue
segment tree
rb tree
prefix sum
treap/cartesian tree
disjoint set
strongly connected components
backtracking
monotone queue
using treez::queue_monotone::QueueMonotone;
letmut q : QueueMonotone<i32>= QueueMonotone::new();
const window : usize=20;
q.set_auto_len(window);
letmut rng = rand::thread_rng();
let arr : Vec<i32>= (0..100).map(|x| rng.gen_range(-1000,1000)).collect();
for (i,v) in arr.iter().enumerate() {
q.push(*v);
let bound_left = std::cmp::max((i+1).saturating_sub(window),0);
let m =*q.max().expect("max");
assert_eq!(m, *arr[bound_left..=i].iter().max().unwrap());
}
segment tree
//summation segment treeletmut seg = SegSum::new(0, m); //range: [0,m), subsequent operations have to be within this rangelet delta : T = ... //T: Add<Output=T> + Mul<i64, Output<T>> + Clone + Default + Debug
seg.add(a, b, &delta); //add delta to range [a,b)
seg.update(a, b, &val); //set range [a,b) to val
...
let v : T = seg.query_range(i, j); //query sum in range [i,j)//max segment treeletmut seg = SegMax::new(0, m); //range: [0,m), subsequent operations have to be within this rangelet delta : T = ... //T: Add<Output=T> + Ord + Debug + Clone + Min//eg: implMinfori64 {
fnmin() -> i64 {
i64::MIN
}
}
seg.add(a, b, &delta); //add delta to range [a,b)
seg.update(a, b, &val); //set range [a,b) to max(val,element[i]) for i in [a,b)
...
let v : T = seg.query_range(i, j); //query max in range [i,j)
red black tree
letmut t : treez::rb::TreeRb<isize, isize>= treez::rb::TreeRb::new();
for i in0..nums.len() {
let r = nums[i];
t.insert( r, i asisize );
}
for i in0..nums.len() {
let r = nums[i];
let v = t.remove( &r ).expect( "remove unsuccessful" );
}
letmut t = treap::NodePtr::new();
{
let v = t.query_key_range( -100., 100. ).iter().
map(|x| x.key()).collect::<Vec<_>>();
assert_eq!( v.len(), 0 );
}
let items =vec![ 56, -45, 1, 6, 9, -30, 7, -9, 12, 77, -25 ];
for i in items.iter() {
t = t.insert( *i asf32, *i ).0;
}
t = t.remove_by_key_range( 5., 10. );
letmut expected = items.iter().cloned().filter(|x|*x <5||*x >=10 ).collect::<Vec<_>>();
expected.sort();
{
let v = t.query_key_range( -100., 100. ).iter().
map(|x| x.key()).collect::<Vec<_>>();
assert_eq!( v.len(), expected.len() );
expected.iter().zip( v.iter() )
.for_each(|(a,b)|assert!(equal_f32( (*a asf32), *b ) ) );
}
let ((t1, t2), node_with_key_0 ) = t.split_by_key(0.);
assert!( node_with_key_0.is_some() );
let t3 = t1.merge_contiguous( t2 );
{
let v = t3.query_key_range( -100., 100. ).iter().
map(|x| x.key()).collect::<Vec<_>>();
assert_eq!( v.len(), expected.len() );
expected.iter().zip( v.iter() )
.for_each(|(a,b)|assert!(equal_f32( (*a asf32), *b ) ) );
}
let va = (100..200).map(|x| (x*2) ).collect::<Vec<i32>>();
letmut t4 = treap::NodePtr::new();
for i in va.iter() {
t4 = t4.insert( (*i asf32), *i ).0;
}
let t5 = t3.union(t4);
let vc = (50..70).map(|x| (x*2) ).collect::<Vec<i32>>();
letmut t6 = treap::NodePtr::new();
for i in vc.iter() {
t6 = t6.insert( (*i asf32), *i ).0;
}
let t7 = t5.intersect( t6 );
disjoint set
letmut v = Dsu::init(10);
//1, 3, 5, 7 ,9for i in0..5 {
let j = i*2+1;
v.merge( j, j-1 );
}
let ret = v.get_sets_repr();
assert_eq!( ret.len(), 5 );
v.merge(5,9);
assert_eq!( v.get_sets_repr().len(), 4 );
lower_bound, upper_bound
same logic as C++ lower/upper_bound; requires item type to have cmp::Ord trait
letmut arr = ...
arr.sort();
let val = ...
let idx = bound::upper_bound(&arr[..], &val);
//idx in [0, arr.size]letmut arr = ...
arr.sort();
let val = ...
let idx = bound::lower_bound(&arr[..], &val);
The Tidelift Subscription provides access to a continuously curated stream of human-researched and maintainer-verified data on open source packages and their licenses, releases, vulnerabilities, and development practices.