Dynamic range maximum query

bit.c

saidx_t range_max(const saidx_t *restrict data,
                  const saidx_t *restrict left_tree,
                  const saidx_t *restrict right_tree,
                  size_t first, size_t last)
{
	assert(first < last);
	saidx_t value = -1;

	for (; (first | first + 1) < last; first |= first + 1)
		if (value < right_tree[first])
			value = right_tree[first];

	if (value < data[first])
		value = data[first];

	for (; --last > first; last &= last + 1)
		if (value < left_tree[last])
			value = left_tree[last];

	return value;
}

void increase(saidx_t *restrict data,
              saidx_t *restrict left_tree,
              saidx_t *restrict right_tree,
              size_t size, size_t i, saidx_t value)
{
	if (data[i] < value)
		data[i] = value;

	for (size_t j = i; j < size; j |= j + 1)
		if (left_tree[j] < value)
			left_tree[j] = value;

	for (size_t j = i; j != (size_t) -1; j = (j & j + 1) - 1)
		if (right_tree[j] < value)
			right_tree[j] = value;
}

segment_tree.c

saidx_t range_max(const saidx_t *segment_tree,
                  size_t inner_node_count,
                  size_t first, size_t last)
{
	saidx_t value = -1;
	size_t left = first + inner_node_count;
	size_t right = last + inner_node_count - 1;
	while (left <= right)
	{
		if (left % 2 && value < segment_tree[left])
			value = segment_tree[left];
		if (!(right % 2) && value < segment_tree[right])
			value = segment_tree[right];
		left = (left + 1) / 2;
		right = (right - 1) / 2;
	}
	return value;
}

void increase(saidx_t *segment_tree, size_t inner_node_count,
              size_t i, saidx_t value)
{
	for (i += inner_node_count; i; i /= 2)
		if (segment_tree[i] < value)
			segment_tree[i] = value;
}

void set(saidx_t *segment_tree, size_t inner_node_count,
         size_t i, saidx_t value)
{
	segment_tree[i += inner_node_count] = value;
	while (i /= 2)
		segment_tree[i] =
			max(segment_tree[i * 2], segment_tree[i * 2 + 1]);
}

Hi, I have a question regarding the increase function in bit.c:

If we update data[i] to a smaller value, both left_tree and right_tree will continue to store the previous (larger) value of data[i] rather than the new smaller one.

That’s why the function is named increase :-) Binary-indexed trees don’t support undoing an update—in this case, decreasing a leaf value. If you need a maximizing tree where your values can both increase and decrease, use the segment tree, which supports setting values.

Of course, you can flip all comparisons and make it range minimum query; then, decreasing will work in the BIT but not increasing.

Maybe this code can make BIT support set values?

https://pastebin.ubuntu.com/p/s53DVHYjvv/

Note also that the implementation of increase specifically never sets data[i] to a smaller value. Effectively, data[i] is the maximum of all values you’ve ever tried to put there.

Maybe this code can make BIT support set values?

Maybe; thanks for the link. At first glance, it seems to recompute each range’s value from scratch and to take asymptotically-the-same logarithmic time but several times more time than the simple increase. At the very least, you’d still want to use increase when you know for sure that the value isn’t decreasing; and I don’t know if it would actually be faster than (a good implementation of) the segment tree. You should try and measure both.