Module data_structure 

data structures

Re-exports

pub use self::partially_retroactive_priority_queue::PartiallyRetroactivePriorityQueue;

pub use self::submask_range_query::SubmaskRangeQuery;

pub use self::treap::Treap;

pub use self::treap::TreapData;

pub use self::union_find::MergingUnionFind;

pub use self::union_find::PotentializedUnionFind;

pub use self::union_find::UndoableUnionFind;

pub use self::union_find::UnionFind;

pub use self::union_find::UnionFindBase;

Modules

accumulate 🔒

allocator 🔒

binary_indexed_tree 🔒

binary_indexed_tree_2d 🔒

binary_search_tree

binary_trie 🔒

bit_vector 🔒

bitset 🔒

bucket_queue 🔒

compress 🔒

compressed_binary_indexed_tree 🔒

compressed_segment_tree 🔒

container 🔒

counter 🔒

dary_heap 🔒

dary_prefix_sum_tree 🔒

dary_segment_tree 🔒

disjoint_sparse_table 🔒

doubly_linked_list 🔒

dual_segment_tree 🔒

fibonacci_hash 🔒

implicit_splay_tree 🔒

implicit_treap 🔒

kdtree 🔒

lazy_segment_tree 🔒

lazy_segment_tree_map 🔒

li_chao_tree 🔒

line_set 🔒

pairing_heap 🔒

partially_retroactive_priority_queue

persistent_segment_tree 🔒

radix_heap 🔒

range_ap_add 🔒

range_fold_with_upper_bound 🔒

range_frequency 🔒

range_map 🔒

range_minimum_query 🔒

segment_tree 🔒

segment_tree_map 🔒

simd

sliding_window_aggregation 🔒

slope_trick 🔒

sparse_set 🔒

splay_operations

splay_tree 🔒

static_range_product 🔒

static_search 🔒

submask_range_query

transducer 🔒

treap

trie 🔒

union_find

vec_map 🔒

wavelet_matrix 🔒

Macros

transducer

build transducer

Structs

AcceptTransducer

Accumulate

Accumlated data

Accumulate2d

2-dimensional accumlated data

AccumulateKd

AlwaysAcceptingTransducer

BTreeCounter

BTreeMapFactory

BinaryIndexedTree

BinaryIndexedTree2D

BinaryTrie

BitSet

BitVector

BitVectorBlock

BoxAllocator

BucketQueueI8

A fixed 8-bit-universe max-priority queue. BinaryHeap::peek_mut can be faster for replacements in tiny queues.

BucketQueueI16

A fixed 16-bit-universe max-priority queue that allocates about 264 KiB when empty. BinaryHeap can be faster for small queues.

BucketQueueU8

A fixed 8-bit-universe max-priority queue. BinaryHeap::peek_mut can be faster for replacements in tiny queues.

BucketQueueU16

A fixed 16-bit-universe max-priority queue that allocates about 264 KiB when empty. BinaryHeap can be faster for small queues.

ChainTransducer

CompressedBinaryIndexedTree

CompressedSegmentTree

DaryHeapI32

A cache-line-oriented 16-ary max-heap for medium-to-large 32-bit heaps. BinaryHeap can be faster for small heaps and monotone replacements.

DaryHeapI64

A cache-line-oriented 8-ary max-heap for large 64-bit heaps. BinaryHeap can be faster for small heaps and monotone replacements.

DaryHeapI128

A cache-line-oriented 4-ary max-heap for large full-width 128-bit heaps. BinaryHeap can be faster for small heaps, monotone replacements, and heavily repeated keys.

DaryHeapU32

A cache-line-oriented 16-ary max-heap for medium-to-large 32-bit heaps. BinaryHeap can be faster for small heaps and monotone replacements.

DaryHeapU64

A cache-line-oriented 8-ary max-heap for large 64-bit heaps. BinaryHeap can be faster for small heaps and monotone replacements.

DaryHeapU128

A cache-line-oriented 4-ary max-heap for large full-width 128-bit heaps. BinaryHeap can be faster for small heaps, monotone replacements, and heavily repeated keys.

DaryPrefixSumTreeU32

A cache-line-oriented d-ary tree for point updates, prefix sums, and prefix searches.

DaryPrefixSumTreeU64

A cache-line-oriented d-ary tree for point updates, prefix sums, and prefix searches.

DarySegmentTreeAddI32

A cache-line-oriented d-ary point-update segment tree for wrapping range sums over i32.

DarySegmentTreeAddI64

A cache-line-oriented d-ary point-update segment tree for wrapping range sums over i64.

DarySegmentTreeMaxI32

A cache-line-oriented d-ary point-update segment tree for range maxima over i32.

DarySegmentTreeMaxI64

A cache-line-oriented d-ary point-update segment tree for range maxima over i64.

DarySegmentTreeMinI32

A cache-line-oriented d-ary point-update segment tree for range minima over i32.

DarySegmentTreeMinI64

A cache-line-oriented d-ary point-update segment tree for range minima over i64.

DequeAggregation

DisjointSparseTable

DoublyLinkedList

Manages only prev/next links of indices.

DualSegmentTree

EqualTransducer

FibonacciHasheru32

FibonacciHasheru64

FixedVecMapFactory

FoldTransducer

FunctionalTransducer

HashCompress

HashCounter

HashMapFactory

HashMapFactoryWithCapacity

IdentityTransducer

ImplicitSplayTree

ImplicitTreap

InitTransducerDp

IntersectionTransducer

IteratorTransducer

LazySegmentTree

LazySegmentTreeMap

LexicographicalTransducer

DFA to accept Less/Greater than (or equal to) in lexicographical order

LiChaoTree

LineSet

MapTransducer

MemoryPool

MonoidalTransducer

OfflineLiChaoTree

PairingHeap

PersistentSegmentTree

ProductTransducer

QueueAggregation

RadixHeapU32

A min-priority queue whose removed keys are monotonically nondecreasing.

RadixHeapU64

A min-priority queue whose removed keys are monotonically nondecreasing.

RangeArithmeticProgressionAdd

RangeFoldWithUpperBound

Offline range folds over entries whose keys are at most a query bound.

RangeFrequency

RangeMap

A map to control intervals that have same values.

RangeMinimumQuery

RangeSet

A set to control intervals.

RetainTransducer

RevLexicographicalTransducer

DFA to accept Less/Greater than (or equal to) in reversed lexicographical order

RevSequenceTransducer

SegmentTree

SegmentTreeMap

SequenceTransducer

SlopeTrick

SparseSet

SplayTree

Static2DTree

StaticRangeProduct

StaticSearch

A static search index over sorted integer or integer-encoded keys.

Transducerdp

Trie

TryFoldTransducer

TryMapTransducer

VecCompress

VecMap

VecMapFactory

VecMapFactoryWithCapacity

WaveletMatrix

WaveletMatrixPointAdd

Traits

Allocator

Compressor

Container

ContainerEntry

ContainerFactory

LiChaoLine

OrderedCompressor

RankSelectDictionaries

rank_i(select_i(k)) = k rank_i(select_i(k) + 1) = k + 1

SimdKey

Maps a key to an unsigned integer with exactly the same ordering.

Transducer

Type Aliases

CompressedBinaryIndexedTree1d

CompressedBinaryIndexedTree2d

CompressedBinaryIndexedTree3d

CompressedBinaryIndexedTree4d

CompressedSegmentTree1d

CompressedSegmentTree2d

CompressedSegmentTree3d

CompressedSegmentTree4d

FibHashMap

FibHashSet

FibonacciHasher