Skip to content

feat: struct IntervalSet #2

@TrueRyoB

Description

@TrueRyoB

features:
let...

  • N be the size of ranges inside the struct
  • k be the size of output
  1. IntervalSet(ll L, ll R): $O(1)$
  2. template<T> void insert(T L, T R) : $O(\log{N})$
  3. template<T> T remove(T L, T R): $O(\log{N})$
  4. template<T> T covered_length(): $O(\log{N})$
  5. template<T> T covered_length(T L, T R): $O(\log{N})$
  6. template<T> int size(): $O(\log{N})$
  7. template<T> int size(T L, T R): $O(\log{N})$
  8. bool intersects(T L, T R): $O(\log{N})$
  9. bool contains(T i): $O(\log{N})$
  10. vector<pair<T,T>> enumerate(T L, T R): $O(k+ \log{N})$

if I am still feeling okay...

  • split
  • next_gap
  • next_interval
  • clear
  • ~IntervalSet()

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions