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

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

Looking at the "Mo-based solution" of problem 1000F - Одно вхождение 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.

Tags set, advanced data structure

History

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