# Questions tagged [data-structures]

Questions about ways of storing data so that it can be used advantageously by algorithms.

361 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
155 views

### I need a better data structure than a graph with condition nodes

Suppose i have a cyclic weighted ($\mathbb{Z}$) directed graph where nodes are either simple or complex. a simple node is just a usual node whilst a complex node is a node that contains a set of ...
384 views

### Expected depth of modified kind of treap

If we have $n$ elements $s_1, \dots, s_n$ and build a kind of treap (tree-heap) out of it. Each $s_k$ has a priority, which is an integer in $\{ 1, 2, 3 \dots, \lceil \log n \rceil\}$. Since the ...
88 views

### What are the potential uses of a good R.N.S. system?

We can consider a Residue Number System (R.N.S.) that has efficient operations for add, multiply, and compare between two numbers. A more rigorous definition We can suppose that we can perform the ...
190 views

### Recover permutation from prefix sums, using segment trees?

I encountered the following problem on Codeforces. An array of integers $p_1,p_2,…,p_n$ is called a permutation if it contains each number from 1 to n exactly once. For example, the following ...
24 views

2k views

### Interval tree: find all intervals containing a given interval

Given an interval tree $T$ and an interval $I$, I need to find an algorithm that returns all intervals in $T$ that contain $I$. The asymptotic running time should be $O(min(n,(k + 1) log n))$ where $k$...
91 views

### Given a permutation of n integers, how fast can a corresponding Standard Young's Tableau be created?

The Schensted insertion algorithm has an $O(n^2)$ running time, for constructing such a standard Young's Tableaux. But, since every permutation has a unique Young's tableau, there seems no reason as ...
649 views

### Time complexity of the operations on a b-tree if deletion is performed by marking nodes inactive

I'm given a B-tree where the delete-operation is not implemented, but instead keys are deleted using tombstones (so they stay in the tree, but are marked as deleted). Now when at least 90% of all keys ...
357 views

### Unique integer priority queue with both $O(1)$ insert and extract-min?

I'm aware of the two questions prioritizing inserts and extracts individually, each in $O(1)$ time, but does there exist a unique integer priority queue algorithm for the range $[0, n)$ that can do ...
63 views

### Correct bracketing check with rotate operation on position i

Given sequence (length $N$) of brackets like $($ and $)$. The task is to implement data structure which supports following operations: Check whether the sequence is correctly bracketed Rotate bracket ...
96 views

### Array counter with mimimum find

I need to implement data strucure such as array, but with the following interface: GetMin() - Returns the minimum from the array IncRight(index) - Increases all values from specified index to the end ...
82 views

### What are the substitues for Kolmogorov Complexity to analyse Hashing

The paper "Monotone Minimal Perfect Hashing: Searching a Sorted Table with O(1) Accesses" <http://www.itu.dk/people/pagh/papers/sparse.pdf> is the only one that uses Kolmogorov Complexity to obtain ...
683 views

### Some confusion about segment tree and line sweep method for finding area of union of axis parallel rectangles

I am having some confusion about finding the area of union of $n$ axis parallel rectangles in $O(n\log n)$ by the line sweep method. The following pictures are from the book of Shamos and Preparata. ...
423 views

Are there any known "adaptive data structures", for example, which can change on-fly from array to linked-list, or from the latter to binary tree depending on access patterns to it? For example: small ...
Assume an ordered set $M = \{\tau_1, \tau_2, ..., \tau_n\}$ and a subset $S = \{\tau_k,\tau_l,...,\tau_m\}\subset M$ where $1\leq k,l,m \leq n$. All the items of $S$ are randomly ordered. The task is ...