On an array of sets, Data structure to handle Interval insert, Interval erase, Interval sum of size query

Question

Consider an array of sets. As you know a set must not have multiple elements. I need a data structure to handle following queries:

1. Insert element x to all sets on interval [ L, R ].
2. Erase element x from all sets on interval [ L, R ].
3. Query the sum of sizes of sets on interval [ L, R ] of the array.

Is there any data structure to handle it in something better than $O(n \cdot q)$ Time/Memory complexity? (Something like $q \cdot log(n)$, $q \cdot \log ^ 2(n)$ or $q \cdot sqrt(n)$ where $q$ is the number of queries and $n$ is the size of the array).

Update: interval [ L, R ] means the interval of indices of the array from index L to index R.

Answer 1

I am assuming that inserting a value $x$ to a set already containing it does nothing, which is how sets usually work. Then this can be solved in amortised $\mathcal{O}(\log n \log q)$ time per query, with $\mathcal{O}(n + q \log n)$ memory usage.

Assume you have $n = 2^{h}$ sets (this is not limiting, add some unused sets if you need to). We will build a segment tree on the sets: build a perfect binary tree of size $2n-1$, and index the nodes such that node $1$ is the root, the children of node $i$, $1 \leq i < n$ are nodes $2i$ and $2i+1$, and nodes $n, \dots, 2n-1$ are the leaves. Each vertex represents some interval of the sets, with leaf $i+n$, $0 \leq i < n$ representing the $i$th original set (0-indexed), and each vertex representing the union of the intervals its children represent.

We will store in every node two sets: one containing every value occurring in every set of its interval, but not in every set of its parent's interval, called $all[i]$, and one containing every value occurring in some, but not all of the sets in its interval, called $some[i]$. We also store an integer $sum[i]$, which is $|all[i]|$ times the size of the node's interval, plus the sums of its children.

First note that this data is sufficient to answer queries of type 3 in $\mathcal{O}(\log n)$ time. Say we want to count the total size of the sets in interval $[a, b]$. DFS down from the root, and at every node,

• If that node's interval is disjoint of $[a, b]$, return 0
• If that node's interval is contained in $[a, b]$, return $sum[i]$.
• Otherwise, return $|all[i]|$ times the size of the intersection of $[a, b]$ and this node's interval, plus the return values of recursive calls to this node's children.

Clearly storing the data this way requires at most $\mathcal{O}(n + q \log n)$ memory:

• We initially need $\mathcal{O}(n)$ memory.
• In a query of type 1, we at worst add $x$ to $\mathcal{O}(\log n)$ sets in our tree, since in segment trees, for any interval $[a, b]$ there are at most $\mathcal{O}(\log n)$ nodes, such that their interval is contained in $[a, b]$, but the interval of their parent isn't.
• In a query of type $2$, say we delete $x$ from interval $[a, b]$. If $x$ doesn't occur in $a-1$ and doesn't occur in $b+1$, this operation in fact frees memory. Thus it always uses at most as much memory as two insertions, as we can extend the interval to be deleted until $x$ doesn't occur in $a-1$ and $b+1$, and then re-insert $x$ to the sides.
• Queries of type $3$ are read-only, and use no memory.

How to perform operations 1 and 2? First note that we do everything in DFS-order, so updating the stored value is trivial: it's just the sum of the stored values of this node's children, plus the size of this node's interval times the size of this node's first set. So we only need to consider how to update the sets.

For this time complexity, we need amortised analysis. We will use a potential function with value

\begin{equation*} f = \sum_{i = 1}^{2n-1} |some[i]| \log q \end{equation*}

With this potential function, it costs no time to delete $x$ from interval $[a, b]$, if $[a, b]$ is the interval of some node $i$, and $x \in some[i]$, and we do not care about updating ancestors of $i$ for now. Deleting $x$ from $some[i]$ takes $\mathcal{O}(\log q)$ time, but the potential decreases by $\log q$. Then recurse to the children of $i$. If $x \not \in some[j]$ for either child $j$, then if $x \in all[j]$, delete $x$ from $all[j]$, otherwise return. This wastes $\log q$ time, but with large enough constants, the potential decrease covers that.

In operation 1, say we want to insert $x$ to interval $[a, b]$. We DFS down from the root, and at every node,

• If that node's interval is disjoint of $[a, b]$, return.
• If that node's interval is contained in $[a, b]$, first delete $x$ from the interval for either free if $x \in some[i]$, or at the cost of $\mathcal{O}(\log q)$ otherwise, then add $x$ to $all[i]$ in $\mathcal{O}(\log q)$.
• Otherwise, first recurse to the node's children. Then, update whether $x$ appears in $all[i]$ and $some[i]$ in $\mathcal{O}(\log q)$ time. If $x \in all[j]$ for both children $j$, you have to remove it from $all[j]$ for both children, but this is again just $\mathcal{O}(\log q)$ time.

Thus insertion takes $\mathcal{O}(\log n \log q)$ amortised time, since cases 2 and 3 occur at most $\mathcal{O}(\log n)$ times. For deletion, very similarly, we again DFS and at every node,

• If that node's interval is disjoint of $[a, b]$, return.
• If that node's interval is contained in $[a, b]$, delete $x$ from the interval for either free if $x \in some[i]$, or at the cost of $\mathcal{O}(\log q)$ otherwise.
• Otherwise, first recurse to the node's children. Then, update whether $x$ appears in $all[i]$ and $some[i]$ in $\mathcal{O}(\log q)$ time.

Here's a C++ implementation:

#include <iostream>
#include <vector>
#include <set>
using namespace std;
using ll = long long;

class SegTree {
    private:
        vector<set<int>> all, some;
        vector<ll> sum;
        int h = 1;

        // returns 2 if x in all[i], 1 if x in some[i] and otherwise 0
        int val(int i, int x) {
            return all[i].count(x) ? 2 : some[i].count(x);
        }
        void update(int i, int x, int len) {
            int va = val(2*i, x), vb = val(2*i+1, x);
            if (va == 2 && vb == 2) {
                some[i].erase(x);
                all[i].insert(x);
                for (int c : {2*i, 2*i+1}) {
                    all[c].erase(x);
                    sum[c] -= len / 2;
                }
            } else {
                all[i].erase(x);
                if (va || vb) some[i].insert(x);
                else some[i].erase(x);
            }
            sum[i] = (ll)all[i].size() * len + sum[2*i] + sum[2*i+1];
        }

        // [a, b) is query interval, [ia, ib) is the node's interval
        ll recGet(int a, int b, int i, int ia, int ib) {
            if (b <= ia || ib <= a) return 0; // intervals are disjoint
            if (a <= ia && ib <= b) return sum[i]; // contained in query interval
            int mid = (ia + ib) >> 1;
            ll res = (ll)all[i].size() * (min(ib, b) - max(ia, a));
            res += recGet(a, b, 2*i, ia, mid);
            res += recGet(a, b, 2*i+1, mid, ib);
            return res;
        }

        void recErase(int a, int b, int x, int i, int ia, int ib) {
            int v = val(i, x);
            if (b <= ia || ib <= a || v == 0) return;
            if (v == 2) {
                all[i].erase(x);
                sum[i] -= ib - ia;
                if (ia < a) recInsert(ia, a, x, i, ia, ib);
                if (b < ib) recInsert(b, ib, x, i, ia, ib);
            } else {
                int mid = (ia + ib) >> 1;
                recErase(a, b, x, 2*i, ia, mid);
                recErase(a, b, x, 2*i+1, mid, ib);
                update(i, x, ib-ia);
            }
        }

        void recInsert(int a, int b, int x, int i, int ia, int ib) {
            if (b <= ia || ib <= a || all[i].count(x)) return;
            if (a <= ia && ib <= b) {
                if (some[i].count(x)) recErase(a, b, x, i, ia, ib);
                all[i].insert(x);
                sum[i] += ib - ia;
            } else {
                int mid = (ia + ib) >> 1;
                recInsert(a, b, x, 2*i, ia, mid);
                recInsert(a, b, x, 2*i+1, mid, ib);
                update(i, x, ib-ia);
            }
        }
    public:
        SegTree(int n) {
            while(h < n) h <<= 1;
            all.resize(2*h);
            some.resize(2*h);
            sum.resize(2*h, 0);
        }

        ll query(int a, int b) { return recGet(a, b+1, 1, 0, h); }
        void erase(int a, int b, int x) { recErase(a, b+1, x, 1, 0, h); }
        void insert(int a, int b, int x) { recInsert(a, b+1, x, 1, 0, h); }
};

int main() {
    int n, q;
    cin >> n >> q;

    SegTree seg(n);
    for (int i = 0; i < q; ++i) {
        int t, a, b;
        cin >> t >> a >> b;
        --a; --b;

        if (t == 3) {
            cout << seg.query(a, b) << '\n';
        } else {
            int x;
            cin >> x;
            if (t == 1) seg.insert(a, b, x);
            else seg.erase(a, b, x);
        }
    }
}
```

Answer 2

You can achieve an $O(\log(n))$ time complexity per each query with $O(M \cdot \log(n))$ memory footprint, where M is a maximum number of elements which were simultaneously stored in our data structure.

The main idea is to use segment tree with lazy propagation and store a pair $<Set, sz>$ in each node of this tree. Where $Set$ is a set (presented by hash table) of all elements which belong to all sets of corresponding segment. And $sz$ is a sum of sizes of all sets of a corresponding segment.