Return to 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).

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.

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

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

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 * q) Time/Memory complexity? (Something like q * log(n), q * log ^ 2 (n) or q * sqrt(n) where q is the number of queries).

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