segment_tree.c File Reference

segment trees with only point updates More...

#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

Include dependency graph for segment_tree.c:

Data Structures
struct	segment_tree
	This structures holds all the data that is required by a segment tree. More...

Typedefs
typedef void(*	combine_function) (const void *a, const void *b, void *result)
	Function that combines two data to generate a new one The name of function might be misleading actually combine here signifies the fact that in segment trees we take partial result from two ranges and using partial results we derive the result for joint range of those two ranges For Example: array(1,2,3,4,5,6) sum of range [0,2] = 6 and sum of range [3,5] = 15 the combined sum of two range is 6+15=21.
typedef struct segment_tree	segment_tree
	This structures holds all the data that is required by a segment tree.

Functions
void	segment_tree_build (segment_tree *tree)
	Builds a Segment tree It is assumed that leaves of tree already contains data.
void	segment_tree_update (segment_tree *tree, size_t index, void *val)
	For point updates This function updates the element at given index and also updates segment tree accordingly.
void	segment_tree_query (segment_tree *tree, long long l, long long r, void *res)
	Query the segment tree This function helps in range query of segment tree This function assumes that the given range is valid Performs the query in range [l,r].
segment_tree *	segment_tree_init (void *arr, size_t elem_size, size_t len, void *identity, combine_function func)
	Initializes Segment Tree Accquires memory for segment tree and fill the leaves of segment tree with data from array.
void	segment_tree_dispose (segment_tree *tree)
	Dispose Segment Tree Frees all heap memory accquired by segment tree.
void	segment_tree_print_int (segment_tree *tree)
	Prints the data in segment tree The data should be of int type A utility to print segment tree with data type of int.
void	minimum (const void *a, const void *b, void *c)
	Utility for test A function compare for minimum between two integers This function is used as combine_function for RMQ.
static void	test ()
	Test RMQ Testing Segment tree using Range Minimum Queries.
int	main ()
	Main Function.

Detailed Description

segment trees with only point updates

This code implements segment trees. Segment trees are general structures which allow range based queries in a given array in logN time. Segment tree with point updates allow update of single element in the array in logN time. Learn more about segment trees here

Author

Lakhan Nad

Typedef Documentation

combine_function

typedef void(* combine_function) (const void *a, const void *b, void *result)

Function that combines two data to generate a new one The name of function might be misleading actually combine here signifies the fact that in segment trees we take partial result from two ranges and using partial results we derive the result for joint range of those two ranges For Example: array(1,2,3,4,5,6) sum of range [0,2] = 6 and sum of range [3,5] = 15 the combined sum of two range is 6+15=21.

Note

The function is same to binary function in Discrete Mathematics

Parameters

a	pointer to first data
b	pointer to second data
result	pointer to memory location where result of combining a and b is to be stored

Function Documentation

main()

int main

(

void

)

Main Function.

Returns

0 on exit

{
    test();
    return 0;
}

Here is the call graph for this function:

minimum()

void minimum	(	const void *	a,
		const void *	b,
		void *	c
	)

Utility for test A function compare for minimum between two integers This function is used as combine_function for RMQ.

Parameters

a	pointer to integer a
b	pointer to integer b
c	pointer where minimum of a and b is tored as result

{
    *(int *)c = *(int *)a < *(int *)b ? *(int *)a : *(int *)b;
}

segment_tree_build()

void segment_tree_build

(

segment_tree *

tree

)

Builds a Segment tree It is assumed that leaves of tree already contains data.

Parameters

tree	pointer to segment tree to be build

{
    size_t elem_size = tree->elem_size;
    int index = (tree->length - 2);
    size_t b, l, r;
    char *ptr = (char *)tree->root;
    for (; index >= 0; index--)
    {
        b = index * elem_size;
        l = (2 * index + 1) * elem_size;
        r = (2 * index + 2) * elem_size;
        tree->combine(ptr + l, ptr + r, ptr + b);
    }
}

segment_tree_dispose()

void segment_tree_dispose

(

segment_tree *

tree

)

Dispose Segment Tree Frees all heap memory accquired by segment tree.

Parameters

tree	pointer to segment tree

{
    free(tree->root);
    free(tree->identity);
}

segment_tree_init()

segment_tree * segment_tree_init	(	void *	arr,
		size_t	elem_size,
		size_t	len,
		void *	identity,
		combine_function	func
	)

Initializes Segment Tree Accquires memory for segment tree and fill the leaves of segment tree with data from array.

Parameters

arr	the array data upon which segment tree is build
elem_size	size of each element in segment tree
len	total no of elements in array
identity	the identity element for combine_function
func	the combine_function used to build segment tree

Returns

pointer to sgement tree build

{
    segment_tree *tree = malloc(sizeof(segment_tree));
    tree->elem_size = elem_size;
    tree->length = len;
    tree->combine = func;
    tree->root = malloc(sizeof(char) * elem_size * (2 * len - 1));
    tree->identity = malloc(sizeof(char) * elem_size);
    char *ptr = (char *)tree->root;
    memset(ptr, 0, (len - 1) * elem_size);  // Initializing memory
    ptr = ptr + (len - 1) * elem_size;
    memcpy(ptr, arr, elem_size * len);  // copy the leaf nodes i.e. array data
    memcpy(tree->identity, identity, elem_size);  // copy identity element
    return tree;
}

Here is the call graph for this function:

segment_tree_print_int()

void segment_tree_print_int

(

segment_tree *

tree

)

Prints the data in segment tree The data should be of int type A utility to print segment tree with data type of int.

Parameters

tree	pointer to segment tree

{
    char *base = (char *)tree->root;
    size_t i = 0;
    for (; i < 2 * tree->length - 1; i++)
    {
        printf("%d ", *(int *)(base + i * tree->elem_size));
    }
    printf("\n");
}

segment_tree_query()

void segment_tree_query	(	segment_tree *	tree,
		long long	l,
		long long	r,
		void *	res
	)

Query the segment tree This function helps in range query of segment tree This function assumes that the given range is valid Performs the query in range [l,r].

Parameters

tree	pointer to segment tree
l	the start of range
r	the end of range
res	the pointer to memory where result of query is stored

{
    size_t elem_size = tree->elem_size;
    memcpy(res, tree->identity, elem_size);
    elem_size = tree->elem_size;
    char *root = (char *)tree->root;
    l += tree->length - 1;
    r += tree->length - 1;
    while (l <= r)
    {
        if (!(l & 1))
        {
            tree->combine(res, root + l * elem_size, res);
        }
        if (r & 1)
        {
            tree->combine(res, root + r * elem_size, res);
        }
        r = (r >> 1) - 1;
        l = (l >> 1);
    }
}

segment_tree_update()

void segment_tree_update	(	segment_tree *	tree,
		size_t	index,
		void *	val
	)

For point updates This function updates the element at given index and also updates segment tree accordingly.

Parameters

tree	pointer to segment tree
index	the index whose element is to be updated (0 based indexing used)
val	pointer to value that is to be replaced at given index

{
    size_t elem_size = tree->elem_size;
    index = index + tree->length - 1;
    char *base = (char *)tree->root;
    char *t = base + index * elem_size;
    memcpy(t, val, elem_size);
    while (index > 0)
    {
        index = ((index - 1) >> 1);
        tree->combine(base + (2 * index + 1) * elem_size,
                      base + (2 * index + 2) * elem_size,
                      base + index * elem_size);
    }
}

test()

static void test ( void  )

static

Test RMQ Testing Segment tree using Range Minimum Queries.

Returns

void

{
    int32_t arr[10] = {1, 0, 3, 5, 7, 2, 11, 6, -2, 8};
    int32_t identity = __INT32_MAX__;
    segment_tree *tree =
        segment_tree_init(arr, sizeof(*arr), 10, &identity, minimum);
    segment_tree_build(tree);
    int32_t result;
    segment_tree_query(tree, 3, 6, &result);
    assert(result == 2);
    segment_tree_query(tree, 8, 9, &result);
    assert(result == -2);
    result = 12;
    segment_tree_update(tree, 5, &result);
    segment_tree_update(tree, 8, &result);
    segment_tree_query(tree, 0, 3, &result);
    assert(result == 0);
    segment_tree_query(tree, 8, 9, &result);
    assert(result == 8);
    segment_tree_dispose(tree);
}

Here is the call graph for this function: