SharpUtils

C# Data Structures and Algorithm Library

Data Classes:

• Complex - complex number implementation with operator overloads

• DisjointSet - disjoint-set with almost constant amortized time per operation link

• Heap<T> - heap link

• MultiSet<T> - C# implementation of std::multiset link

• Quaternion - quaternion implementation with operator overloads

• RBTree<K, V, A> - red-black tree with augmentation link

• SegTree<T> - segment (interval) tree, which allows custom associative function link

• SuffixTree<T> - suffix tree with O(n) construction link link

• Trie<T> - prefix tree link

Algorithms:

• Arrays:

  • MaxCommonSubstring - longest common substring for up to 64 words in O(n) link
  • RMQ - range minimal query (with sparse table) in O(1) query time and O(n log n) preprocessing time
  • ZFunc - Z algorithm link

• Combinatorics:

  • inversion count, next permutation

• FFT - Fast Fourier Transform link

• Geometry:

  • Convex hull - Andrew's algorithm in O(n log n) link

  • area, line intersection, linear transformation, distance from point to line

• Graph:

  • FloydWarshal - all pairs shortest paths link

  • Dijkstra - single source shortest path link

  • Dinitz - maximum flow in O(V^2 * E) link

• Number Theory:

  • base conversion, Euler totient function, prime factorization, greatest common divisor, fast exponentiation