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]);
}

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.