#include <stdio.h>
#include <stdlib.h>
/*
/*
This file is both C and Markdown.
The data structure you are looking for needs to answer "three-sided
range queries". They are called three-sided because you can picture
your array as representing n points in a two-dimensional set, where
the x coordinate is the array index and the y coordinate is the value
at that index; your query then amounts to "print all of the y
coordinates of points (x,y) where i <= x <= j and y > X". This is
three inequalities on the values printed.
One very simple data structure that can support three-sized range
queries is a priority search tree (PST).
*/
typedef struct NODE {
int y_max;
struct NODE *left, *right;
} Node;
/*
For your usage, you can use a very simple priority search tree. The
tree will have 2*n - 1 nodes. Leaf nodes are associated with a single
location in the array. Non-leaf nodes are associated with a contiguous
region of the array. The association is as follows:
The root is associated with the whole array: positions [0, n)
The left child of a node with range [a,b) is associated with
positions [a, floor((a + b)/2))
The right child of a node with range [a,b) is associated with
positions [floor((a+b)/2), b)
If a region is empty, no node is stored for it.
The association is implicit and not stored anywhere; it can be
inferred from n and the shape of the tree.
Each node additionally stores the maximum value among all of the
values stores in its associated region.
For instance, if your array is {60, 70, 80, 90, 100}, then the tree
nodes and their associated regions and values are:
[0,5):100
/ \
[0,2):70 [2,5):100
/ \ / \
[0,1):60 [1,2):70 [2,3):80 [3,5):100
/ \
[3,4):90 [4,5):100
Constructing a PST takes linear time using recursion:
*/
int Max(int x, int y) { return x > y ? x : y; }
Node * Construct(int n, int ys[]) {
if (!n) return NULL;
Node *result = malloc(sizeof(Node));
if (1 == n) {
result->y_max = ys[n];
result->left = result->right = NULL;
} else {
// To find y_max, we first recurse:
result->left = Construct(n / 2, ys);
result->right = Construct(n - n / 2, ys + n / 2);
// The the y_max is the max of the child y_max values:
result->y_max = Max(result->left->y_max, result->right->y_max);
}
return result;
}
/*
To query a PST, you need to find all leaves of the tree that are in
the given [i, j] region with y_max > X. This can also be done
recursively:
*/
void Query(int a, int b, Node *pst, int i, int j, int X) {
if (!pst || a > j || b < i || pst->y_max <= X) return;
if (b - a == 1) printf("%d ", pst->y_max);
Query(a, (a + b) / 2, pst->left, i, j, X);
Query((a + b) / 2, b, pst->right, i, j, X);
}
/*
A careful accounting shows that the time complexity is O(log n + k),
where k is the number of nodes reported. Note that the lower bound on
any data structure supporting these queries is Ω(k), since
it takes that much time just to print the results.
You can find many careful accountings by just Googling "priority
search tree".
The data structure above is sub-optimal in a number of ways, but it is
simple to explain this way. It can be organized to be stored in an
array of size n/2 + O(1), rather than Θ(n) tree nodes as above.
Updates can be performed in O(log n) time by traversing down the tree
recursively and rebuilding y_max on the way back up:
*/
void Update(int i, int v, int a, int b, Node *pst) {
if (a + 1 == b) {
pst->y_max = v;
return;
}
// Recurse down one subtree:
int mid = (a + b) / 2;
if (i < mid) {
Update(i, v, a, mid, pst->left);
} else {
Update(i, v, mid, b, pst->right);
}
pst->y_max = Max(pst->left->y_max, pst->right->y_max);
}
