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