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
  • func (ps PartialSum) AllSum() uint64
  • func (ps PartialSum) Find(val uint64) (ind uint64, offset uint64)
  • func (ps *PartialSum) IncTail(ind uint64, val uint64)
  • func (ps PartialSum) Lookup(ind uint64) (val uint64)
  • func (ps PartialSum) LookupAndSum(ind uint64) (val uint64, sum uint64)
  • func (ps PartialSum) MarshalBinary() (out []byte, err error)
  • func (ps PartialSum) Num() uint64
  • func (ps PartialSum) Sum(ind uint64) (sum uint64)
  • func (ps *PartialSum) UnmarshalBinary(in []byte) (err error)

Types

type PartialSum

type PartialSum struct {
	// contains filtered or unexported fields
}

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

New returns a new partial sum data struct

func (PartialSum) AllSum

func (ps PartialSum) AllSum() uint64

AllSum returns the sum of all vals

func (PartialSum) Find

func (ps PartialSum) Find(val uint64) (ind uint64, offset 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.

func (*PartialSum) IncTail

func (ps *PartialSum) IncTail(ind uint64, val uint64)

IncTail adds: V[ind] += val ind should hold ind >= Num

func (PartialSum) Lookup

func (ps PartialSum) Lookup(ind uint64) (val uint64)

Lookup returns V[i] in O(1) time

func (PartialSum) LookupAndSum

func (ps PartialSum) LookupAndSum(ind uint64) (val uint64, sum uint64)

LookupAndSum returns V[i] and V[0]+V[1]+...+V[i-1] in O(1) time

func (PartialSum) MarshalBinary

func (ps PartialSum) MarshalBinary() (out []byte, err error)

MarshalBinary encodes VecString into a binary form and returns the result.

func (PartialSum) Num

func (ps PartialSum) Num() uint64

Num returns the number of vals

func (PartialSum) Sum

func (ps PartialSum) Sum(ind uint64) (sum uint64)

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

func (*PartialSum) UnmarshalBinary

func (ps *PartialSum) UnmarshalBinary(in []byte) (err error)

UnmarshalBinary decodes the FixVec form a binary from generated MarshalBinary