A set of integers with O(1) insert, erase, find and O(size) iterate

Revision en1, by rotavirus, 2019-06-13 23:30:14

Looking at the "Mo-based solution" of problem 1000F - One Occurrence in editorial, I noticed the author used some sqrt-decomposition to find any element in the set, but the author could do this in O(1) time using the data structure i'll describe right now.

The set which can contain integers from 1 to $n$ is stored as two arrays of length $O(n)$:

type set struct {
index []int
val []int
size int
}

func newSet(n int) set {
return set{make([]int,1+n),make([]int,1+n),0}
}

func (s *set) Size() int {
return s.size
}


Inserting into the set:

func (s *set) Insert(x int) error {
n := len(s.index)-1
if x<1 || x>n {
return errors.New("inappropriate value to insert")
}
if s.index[x] != 0 {
return errors.New("value already exists in the set")
}

s.size++
s.val[s.size] = x
s.index[x] = s.size

return nil
}


Erasing from the set:

func (s *set) Erase(x int) error {
n := len(s.index)-1
if x<1 || x>n {
return errors.New("inappropriate value to erase")
}
if s.index[x] == 0 {
return errors.New("value already doesn't exist in the set")
}

i := s.index[x]
if i == s.size {
s.val[s.size] = 0
s.index[x] = 0
s.size--
} else {
y := s.val[s.size]
s.val[s.size] = 0
s.index[y] = i
s.val[i] = y
s.index[x] = 0
s.size--
}
return nil
}


Finding an element in the set:

func (s *set) Find (x int) bool {
n := len(s.index)-1
if x<1 || x>n {
return false
}
return s.index[x]>0
}


Iterating over the set:

func (s *set) ToArray() []int {
return s.val[1:1+s.size]
}

func (s *set) ValueAt(i int) int {
return s.val[i-1]
}


However this set doesn't store values in the ascending order like the standard RB-tree set does.

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 rotavirus 2019-06-13 23:30:14 2152 Initial revision (published)