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
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
1answer
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 ...
2
votes
1answer
24 views

Data structure for or-lookups over bit-field associations maps

For a mapping between a bit-arrays and values I want cheap lookups using bitwise-or instead of equality. Slightly more formally, I have a set of associations $k_i \mapsto v_i$ where $k_i \in \mathcal{...
2
votes
0answers
36 views

Graph problem / Dynamic graph

I have been trying to come up with an efficient algorithm for the following problem. Let $G = (V,E)$ be an undirected acyclic weighted graph, where there is exactly one path from a vertex $u$ to any ...
2
votes
0answers
62 views

Counting triplets from three arrays satisfying the equation x^2 = yz

Let's say I have three arrays of positive integers X, Y and Z. You can assume that each of ...
2
votes
0answers
17 views

K-nearest along ray in large point cloud

Are there any well-known data structures known that can handle the following (need to scope whether something is possible): Return the k-closest points to a ray shot through the cloud. Allows quick ...
2
votes
0answers
51 views

Efficiently finding all pairs of disjoint sets

Say we have the letters $\Omega = \{1,2,\dots n\}$, and two sets of subsets of $\Omega$, $S_1, S_2$. I want to find $S_1 \cdot S_2 := \{(s_1,s_2) \in S_1 \times S_2: s_1 \cap s_2 = \emptyset \}$. ...
2
votes
0answers
20 views

Poset data structure to find least element, greater or equal to given

Let $A$ be a finite set, and $S \subset \mathcal{P}(A)$. Is there a data structure for $S$ that would allow to quickly retrieve an element $q \in S $, given a key $p \in \mathcal{P}(A)$, such that $q$ ...
2
votes
0answers
49 views

How to solve following tree problem?

Source of the problem is https://codeforces.com/contest/1152/problem/D . I think i understood the problem , but if possible please explain the problem in simple way and the solution also .I tried very ...
2
votes
0answers
114 views

Data structure & algorithms for super-interval queries on intervals with small integer ends

I would like to have an online data structure that supports inserting an interval, and given a query interval $I_q=[l_q,h_q]$ answer if some interval of the data structure is contained in $I_q$, i.e. ...
2
votes
0answers
23 views

Nested dissection vs kd-tree

Could you explain, please, the difference between the nested dissection and kd-tree. For me they look same representing a tree data structure for a distribution of points in a multi-dimensional ...
2
votes
0answers
115 views

Red-black tree trinode restructuring after insertion and deletion

When performing an insertion/deletion on a red-black tree, how can be argued or proved that it requires at most one/two trinode restructuring(s) respectively? My thoughts so far were: after inserting ...
2
votes
1answer
190 views

Tree traversal with conditional summing values from nodes

Hi all i have algorithmic problem and i struggle with finding optimal solution. I have tree which i want to traverse. Nodes of the tree consist of value and a rank of node (value as well as rank can ...
2
votes
0answers
111 views

Lower bound on online range minimum query with element value modification

Is there a known lower bound to the online Range Minimum Query (RMQ) problem with value modifications (given the array we perform online RMQ on, support dynamically modifying the values of a given ...
2
votes
0answers
50 views

Storing relations space efficiently?

Let $f$ be a binary relation defined on set $S$, which contains numbers from $1$ to $n$. It is also given that number of $|\text{Img}(f)| \le k$. I want to store the function $f$ such in way such that ...
2
votes
0answers
39 views

Documentation of “bin number” trees

TL;DR: I implemented a special (?) binary tree and can't find any further details on the method I used on the internet. I would like to know if there are any scientific papers discussing my ...
2
votes
0answers
34 views

Bug in wikipedia page for Van Emde Boas tree?

The Wikipedia page for vEB trees (specifically the version from 27 September, 2018), gives the following pseudocode for finding the successor element of x in the vEB tree (of universe of size M): <...
2
votes
0answers
86 views

What are some of the simplest applications of heavy hitter problem?

I am learning about stream algorithms and am implementing Count-Min sketch data structure. I am also learning to approximately solve the HH problem with sublinear space complexity. I want to know ...
2
votes
0answers
42 views

Abstract Data Type

I have been studying data structures. In that I have come across topics like Array being defined as Power set of cross product of set of objects and set of natural number and list being defined as ...
2
votes
0answers
298 views

Analysis expected depth of a binary search tree given random values?

I have a guess about the problem above. Suppose I have a binary search tree $T$ initially empty. Suppose I drawn $x_1,\ldots,x_k$ (from some real interval $[a,b]$) keys and I want to insert the keys ...
2
votes
0answers
45 views

Persistent data structure with double and subtract operations

I am seeking a data structure that maintains an array of N numbers and supports the following two operations: Double the first i numbers Subtract the first i numbers of a previous version from the ...
2
votes
0answers
91 views

Splay trees: why are depths of nodes on the access path halved?

The original paper describing splay trees Self-Adjusting Binary Search Trees by Sleator and Tarjan claims that: Splaying not only moves x to the root, but roughly halves the depth of every node ...
2
votes
0answers
1k views

What are efficient data-structures for insert/delete by index?

First of all, a definition of the operations: Insert by index: insert element e at index n, increasing the index of all ...
2
votes
0answers
154 views

Resizing hashmaps and compression functions for hash codes

I am trying to implement a hash table for string keys as part of a university project. I was able to make a basic, working implementation without major issues. I am now trying to optimize the thing to ...
2
votes
0answers
423 views

How much better are conservative updates for count-min sketch?

I've been reading about count-min sketch and I'm interested in the performance of this data structure when doing conservative updates. To my understanding from the Wikipedia article, conservative ...
2
votes
0answers
144 views

How to define the partial or total order of the segments to be inserted in a “sweep-line status” data structure?

I am interested in the details of the implementation of the "sweep-line status" data structure, which is used to implement the Bentley-Ottmann algorithm to find all intersections (and the ...
2
votes
0answers
45 views

Is there an efficient way to insert n items into an n^2 sized heap

I am aware of a O(n) algorithm for constructing a new heap of n items, this is better than repeatedly inserting into an empty heap which takes O(nlogn). I would like to know if there is something ...
2
votes
0answers
98 views

Graph algorithm or framework for determining node affinity based on utilities

I'm looking for an algorithm or framework for thinking about how to determine affinities between nodes. Perhaps affinity is poor choice of wording, but basically I want to use utilities between nodes ...
2
votes
1answer
2k views

Building heaps and heapsort using linked list

I know that linked list is not a appropriate data structure for building heaps but I am interested in knowing the time complexity of building heaps and heapsort using linked list. One of the answers ...
2
votes
0answers
324 views

hash-table subsets

Having trouble figuring this out. If I have 2 sets of integers how would I use a hash table to test if set A is a subset of set B (in pseudocode). I think I understand that basically I would need to ...
2
votes
0answers
27 views

Soft Question: Looking for resources on computation over reals

As the title suggests, I want to take a look at resources (books, lectures or papers) that are available (free or paid) on computation over reals. Thanks in advance!
2
votes
2answers
53 views

Name for type of actions that only care for outcome

There is a definition for kind of actions that only care for outcome. Classic example for such an action is remove from ...
2
votes
0answers
63 views

data structure to store n-tuple keys

I need a good data structure to store the following data: The data are key,value pairs. However, more than one value maps to one key and the key is an n-tuple with n constant. Here's an example: <...
2
votes
0answers
549 views

Finding multi word anagrams from a set of words

Finding all anagrams for a word $w$ from a set of words is a problem with many well-known solutions (for example make a hash table mapping from the bag of letters of a word to the word). But what ...
2
votes
0answers
37 views

Altering the size of a Hash

Does removing the leading(or trailing) n bits of any given hash have any negative effects other then increasing the likeliness of collisions? Does appending 2 hashes of the same object with different ...
2
votes
0answers
250 views

WAVL Trees - Number of rebalances

I was experimenting with a WAVL Tree code I wrote. One thing I noticed is that on average, there was much less rebalancing actions after delete than after insert. In fact, average rebalances after ...
2
votes
0answers
70 views

Finding subsets in a large collection of sets

Given a large collection $\mathcal{X} = \{X_1, X_2, \dots, X_n\}$, where each $X_i$ is a set of integers, what's a fast algorithm to identify all pairs $(i,j)$ with $i \ne j$ such that $X_i \subseteq ...
2
votes
2answers
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$...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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. ...
2
votes
0answers
423 views

“Adaptive” data structure

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 ...
2
votes
0answers
52 views

Are there any practical drop-in replacements for BSTs in the case where data are integers?

There are a number of specialized data structures that implement ordered dictionaries for integer keys: van Emde Boas trees, y-Fast tries, fusion trees, etc. Each of these data structures implement ...
2
votes
0answers
59 views

Ordered set transformation data structure

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

1
2
3 4 5
8