Efficient algorithm for generating data dependency DAG from lists of memory ranges and access modes

Question

Assume you are given:

1. A list of N (not necessarily distinct) memory ranges of the form [x,y], where x and y are non-negative integers representing the lower and upper bounds of the range, and
2. A list of N memory access modes (read or write),

where the $i^{th}$ entry in the memory range list is accessed (either read from or written to) according to the $i^{th}$ entry in the data access modes list.

How do you efficiently generate a data dependency DAG representing the dependencies between subsequent accesses to possibly overlapping memory ranges?

The DAG should not have redundant dependencies. And ideally the algorithm should have running time quadratic in N (or better, if possible).

UPDATE: To clarify, a dependency between two memory accesses exists if

1. The two memory ranges being accessed overlap (i.e., have at least one byte in common), and
2. At least one of the access modes is a write (concurrent reads from the same memory range are ok).

Answer 1

Build an interval tree storing all of the ranges that have been written. That data structure lets you efficiently determine, for any given memory address, the time when it was most recently written.

In particular, scan through the operations in chronological order. When you see a write operation, update the interval tree. Also, for each operation (read or write), check the interval tree to find all intervals that overlap it, and add them to the DAG. This will build up a dependency DAG with no redundancies.

Each update to the tree can be done in $O(\log N)$ time. Also, the overlap check can be done in $O(k + \log N)$ where $k$ is the number of intervals that overlap for that particular query.

The running time will depend on the size of the resulting dependency graph, but if that graph has $M$ edges, then the total running time will be $O(M + N \log N)$. In particular, since this DAG can have at most $O(N^2)$ edges, the algorithm certainly runs in $O(N^2)$ time -- and possibly much faster, if the resulting dependency DAG is sparse.