partialsum

README

partialsum

A Go library for succinct partial sums data structure

PartialSum stores non-negative integers V[0...n) and supports operations in O(1) time using at most (s + n) bits where s is the sum of V[0...n).

PartialSum supports following operations in O(1) time

- IncTail(ind, val) V[ind] += val. ind should be the last one, that is ind >= Num
- Lookup(ind) returns V[ind]
- Sum(ind) returns V[0]+V[1]+...+V[ind-1]
- Find(val) returns ind satisfying Sum(ind) <= val < Sum(ind+1)
	and offset = val - Sum(ind). If there are multiple inds
	satisfiying this condition, return the minimum one.

PartialSum is sutable for storing small (but somethimes large) non-negative integers such as lengths of string.

Note that if we store S[0...n) using interger array (e.g. []uint64), where S[i] = Sum(i), then S requires O(log n) time for Find(), and needs 64n bits.

	PartialSum	[]uint64
Space(bits)	n + s	64n
Lookup	O(1)	O(1)
Sum	O(1)	O(1)
Find	O(1)	O(log n)

partialsum uses rsdic (succinct rank/select dictionary)

Usage

import "github.com/hillbig/partialsum"

ps := partialsum.New()

ps.IncTail(0, 5)
ps.IncTail(2, 4)
ps.IncTail(2, 2)
ps.IncTail(3, 3)

// ps stores [5, 0, 6, 3]
// S = [0, 5, 5, 13, 14]

ps.Num() // 4
ps.AllSum() // 14
ps.Lookup(2) // 6
ps.Sum(2) // 5
ps.Find(5) // 2, 0 because S[2] <= 5 < S[3], and 5 - S[2] = 0

Documentation

Index

• type PartialSum
  • func New() PartialSum

Types

type PartialSum

type PartialSum interface {
	// Increment add V[ind] += val
	// ind should hold ind >= Num
	IncTail(ind uint64, val uint64)

	// Num returns the number of vals
	Num() uint64

	// AllSum returns the sum of all vals
	AllSum() uint64

	// Lookup returns V[i] in O(1) time
	Lookup(ind uint64) (val uint64)

	// Sum returns V[0]+V[1]+...+V[ind-1] in O(1) time
	Sum(ind uint64) (sum uint64)

	// Lookup returns V[i] and V[0]+V[1]+...+V[i-1] in O(1) time
	LookupAndSum(ind uint64) (val uint64, sum uint64)

	// Find returns ind satisfying Sum(ind) <= val < Sum(ind+1)
	// and val - Sum(ind). If there are multiple inds
	// satisfiying this condition, return the minimum one.
	Find(val uint64) (ind uint64, offset uint64)

	// MarshalBinary encodes VecString into a binary form and returns the result.
	MarshalBinary() ([]byte, error)

	// UnmarshalBinary decodes the FixVec form a binary from generated MarshalBinary
	UnmarshalBinary([]byte) error
}

PartialSum stores non-negative integers V[0...N) and supports Sum, Find in O(1) time using at most (S + N) bits where S is the sum of V[0...N)

func New

func New() PartialSum