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

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.

• What's $n\phantom{}$? – Steven Apr 17 at 17:27
• @Steven Of course the size of the array! – amirali Apr 17 at 17:31
• Would you be happy with a time of $O(\log n \cdot \log m )$ per query, where $m$ maximum cardinality of a set? – Steven Apr 17 at 17:33
• @Steven Of course. $log$ of anything will make me happy :) – amirali Apr 17 at 17:35
• @Steven That is also ok. – amirali Apr 17 at 17:35

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);
}
}
}
$$$$

• Please explain what will your solution do for this test case: First add element 1 to all indices which are even, then erase element 1 from [ 1, n ]. If I understand correctly, your solution takes linear time on erasing query, because element 1 should be erased from sets of lowers vertices. If you don't erase it from lower children, you won't answer sum query correctly. – amirali Apr 18 at 5:52
• It does, that's why it's $\mathcal{O}(\log n \log q)$ amortised time. Note that in that case we do $\frac{n}{2} + 1$ operations, but in total only $\mathcal{O}(n \log n)$ work. The definition of "amortised $\mathcal{O}(\log n \log q)$ time per operation" is that for sufficiently large $q$, making $q$ operations takes in total at most $\mathcal{O}(q \log n \log q)$ time. – Antti Röyskö Apr 18 at 6:34
• Correct me if I'm wrong: In insertion and deletion query you recurse to children while the element is available in some[i] and erase the element from all[i]. And you prove that this won't take that much time? And please mention your final time/memory complexity for all of the operations. – amirali Apr 18 at 8:12
• Yes, as the potential function decreases whenever we recurse down after finding a node whose interval is contained in the query interval. Time complexity of both insertion and deletion is amortised $\mathcal{O}(\log n \log q)$, and queries work in $\mathcal{O}(\log n)$. – Antti Röyskö Apr 18 at 10:06

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 $$$$ 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.

• If I understand correctly, The memory complexity is not $O(n \cdot log(n))$. Consider all queries be of type Add new element x to interval [ 1, n ]` Which x hasn't been inserted before. – amirali Apr 17 at 18:58
• Thank you. Fixed it. – Vladislav Bezhentsev Apr 17 at 19:05
• I still think the memory should be $O(n \cdot M)$. In the case I mentioned before, every node of the segment tree will have a set with $M$ elements in it, and there $O(n)$ such nodes, so it should be $O(n \cdot M)$. – amirali Apr 18 at 2:56