README
¶
Goalg
A simple algorithm library with common program quiz utils written in go
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func FastFloatPow ¶
FastFloatPow can compute base**pow in logrithmic time, and return in float64.
Time complexity: O(log(pow)).
func FastModPow ¶
FastModPow can compute base**pow % mod in logarithmic time. mod should be positive and less than 2^32.
If pow is negative, the absolute of the result will less than 1, so 0 will be returned.
Time complexity: O(log(pow)).
func FastPow ¶
FastPow can compute base**pow in logrithmic time. But it may be overflow. If pow is negative, the absolute of the result will less than 1, so 0 will be returned.
If the number is too big, use FastModPow instead.
Time complexity: O(log(pow)).
func FastPrimes ¶
FastPrimes returns all the prime numbers in [2, n) in ascending order.
Time complexity: O(n).
Space complexity: O(n * sizeof(int)).
Ref: https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html.
func Primes ¶
Primes returns all the prime numbers in [2, n) in ascending order.
Time complexity: O(nloglogn).
Space complexity: O(n * sizeof(bool)).
Ref: https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html.
Types ¶
type BIT ¶
type BIT struct {
// contains filtered or unexported fields
}
BIT is the binary indexed tree/Fenwick tree struct.
It's used to calculate prefix sum in logarithmic time with any data updates at any time.
Ref: https://blog.csdn.net/Yaokai_AssultMaster/article/details/79492190.
func NewBIT ¶
NewBIT inits a BIT instance with original data and calculates the prefix sum % mod.
If mod is 0, no mod action will be executed in the future.
Time complexity: O(n).
func (*BIT) PrefixSum ¶
PrefixSum returns the range sum of subarray [0, end].
Time complexity: O(logn).
type DSU ¶
type DSU struct {
// contains filtered or unexported fields
}
DSU is the short for Disjoint Set Union data structure.
Ref: https://cp-algorithms.com/data_structures/disjoint_set_union.html
type Heap ¶
type Heap struct {
// contains filtered or unexported fields
}
Heap , aka PriorityQueue
The top of the heap is the least element sorted by lessFunc function
func NewHeap ¶
NewHeap initials a minimum heap with data and the comparaing function lessFunc.
Time complexity: O(n).
func (*Heap) Pop ¶
func (h *Heap) Pop() interface{}
Pop removes the top element from the heap and heapify itself automatically.
It h.Len() == 0, nil will be returned.
Time complexity: O(logn).
type MXimumStack ¶
type MXimumStack struct {
// contains filtered or unexported fields
}
MXimumStack is a stack with mximum(maximum or minimum) element in the stack recorded
Ref: https://cp-algorithms.com/data_structures/stack_queue_modification.html .
func NewMXimumStack ¶
func NewMXimumStack(lessFunc func(i, j interface{}) bool) *MXimumStack
NewMXimumStack initialize a stack with the comparator lessFunc
func (*MXimumStack) Len ¶
func (m *MXimumStack) Len() int
Len returns the length of the stack.
Time complexity: (O(1)).
func (*MXimumStack) MX ¶
func (m *MXimumStack) MX() interface{}
MX returns the mximum element in the stack
Time complexity: (O(1))
func (*MXimumStack) Pop ¶
func (m *MXimumStack) Pop() interface{}
Pop pops the stack top element.
Time complexity: (O(1)).
func (*MXimumStack) Push ¶
func (m *MXimumStack) Push(d interface{})
Push pushes and records the MX record to the stack.
Time complexity: (O(1))
func (*MXimumStack) Top ¶
func (m *MXimumStack) Top() interface{}
Top returns the stack top element.
Time complexity: (O(1)).
type SparseTable ¶
type SparseTable struct {
// contains filtered or unexported fields
}
SparseTable is fast in multiple range maximum/minimum queries in an immutable array.
Ref: https://cp-algorithms.com/data_structures/sparse-table.html.
func NewSparseTable ¶
func NewSparseTable(data []int, f func(d ...int) int) *SparseTable
NewSparseTable creates a sparse table with the range rule l.
NOTICE: Parameter f must be an idempotent function: https://en.wikipedia.org/wiki/Idempotence. if you want to do range queries in O(1). If not, wrong query results will be returned.
Time complexity: O(nlogn).
func (*SparseTable) QueryRange ¶
func (s *SparseTable) QueryRange(left, right int) int
QueryRange queries the range [left, right] with function f.
Time complexity: O(logn).
func (*SparseTable) QueryRangeFast ¶
func (s *SparseTable) QueryRangeFast(left, right int) int
QueryRangeFast queries the range [left, right] with function f.
NOTICE: Only available if f is an idempotent function: https://en.wikipedia.org/wiki/Idempotence.
Time complexity: O(1).
Source Files