Simple implementation of lazy propagation

lazy_propagation.c

#include <stdlib.h>
#include <math.h>
#include <stdio.h>
#include <string.h>

# define create(type, size) ((type*) malloc(sizeof(type)*size))  //to be used to malloc just to keep code neat

void update_children(int i, int se, int nv);
int *lazy;  // this is lazy propagation

int* buildSegTree(int *arr, int s) { //assume that s is the actual size of the array and not the last index
  //get the height of the tree first 
    int h = ceil(log2(s));
    //get the max_size of the segment tree
    int st_s = 2*pow(2, h)-1;

    printf("Size of ST: %d\n", st_s);

    int *st = create(int, st_s);
    lazy = create(int, st_s); /**/

    memset(lazy, 0, sizeof(int)*st_s);
    memset(st, 0, sizeof(int)*st_s);

    int make_tree(int*, int*, int, int, int);
    make_tree(arr, st, s-1, 0, 1); // we gonna make the root value be at index 1
    return st;

}

#define left_child(index) (2*index)
#define right_child(index) (2*index+1)
int make_tree(int *arr, int *st, int size, int arr_index, int st_index) {
    if (arr_index == size) {
        st[st_index] = arr[arr_index];
        return st[st_index];
    }
    int mid = (arr_index+size)/2;

    int sum = make_tree(arr, st, mid, arr_index, left_child(st_index)) + make_tree(arr, st, size, mid+1, right_child(st_index));
    st[st_index] = sum;
    return sum;
}


int get_sum(int *st, int st_s, int st_e, int st_index, int l, int r) {
    // if (st_e < st_s || st_e < l || st_s > r) return 0;
    // if (st_index >st_e) return 0;

    if (lazy[st_index]) {
        st[st_index] += (st_e-st_s+1)*lazy[st_index];
        if (st_e!=st_s)
            update_children(st_index, st_e, lazy[st_index]);
        lazy[st_index] = 0;
    }

    if(st_s > r || st_e < l)
      return 0;

    if (l <= st_s && r >= st_e)
        return st[st_index];

    int mid = (st_s+st_e) /2;

    return  get_sum(st, st_s, mid, left_child(st_index), l, r)
        + get_sum(st, mid+1, st_e, right_child(st_index), l, r);
}

int sum(int *st, int l, int r, int arr_size) {
    if (l > r || r > arr_size || l < 0)
        return 0; // invalid
    return get_sum(st, 0, arr_size-1, 1, l, r);
}


void update_helper(int *st, int ss, int se, int index, int st_index) {
    if (ss == se) {
        st[st_index] += st[0];
        return;
    }
    int mid = (ss+se)/2;
    int next_st_index = st_index;
    if (index <= mid) {
        se  = mid;
        next_st_index = left_child(st_index);
    }    
else {
        ss = mid+1;
        next_st_index = right_child(st_index);
    }
    st[st_index] += st[0];
    update_helper(st, ss, se, index, next_st_index);
}


void update(int *st, int *arr, int index, int val, int arr_size) {
    if (index < arr_size) {
        int diff = val - arr[index];
        st[0] = diff;
        update_helper(st, 0, arr_size-1, index, 1);
        st[0] = 0;
    }
}

void swap(int *st, int *arr, int i, int j, int arr_size) {
    if (i < arr_size && j < arr_size  && i != j) {
        int temp = arr[i];
        update(st, arr, i, arr[j], arr_size);

        update(st, arr, j, temp, arr_size);
    }
}


// updates values from l ro r inclusive with the new value
//if l<0 or r>array size then we dont satisfy the request
void lazy_range_update(int *st, int l, int r, int arr_size, int new_value) {
    if (l<0 || r > arr_size-1) return;

    int h = ceil(log2(arr_size));
    //get the max_size of the segment tree
    int st_size = 2*pow(2, h)-1;
    void lazy_range_update_helper(int *st, int si, int ss, int se, int us, int ue, int nv);
    lazy_range_update_helper(st, 1, 0, arr_size-1, l, r, new_value);
}

#define in_range(l, r, v) (l<=v && r >=v)

void lazy_range_update_helper(int *st, int si, int ss, int se, int us, int ue, int nv) {

    void update_children(int i, int se, int nv);
    // case 1: if current segment has any updates
    if (lazy[si]) {
        st[si]+=(se-ss+1)*lazy[si];
        if (ss!=se) {
            update_children(si, se, lazy[si]);
        }
        lazy[si] = 0;
    }

    if (se < ss || ss > ue || se < us) return;

    //case 2: If current node's range lies completely in 
    if (ss>=us && se<=ue) {
        //update the current node's range
        //Postpone updates to children by setting  lazy value for children nodes.
        if (ss!=se)
            update_children(si, se, nv);
        st[si] += (se-ss+1)*nv;
        return;
    }

    //case 3: If current node's range overlaps with update range
    int mid = (ss+se)/2;
    /*diff +=*/  lazy_range_update_helper(st, left_child(si), ss, mid, us, ue, nv);
    /*diff +=*/ lazy_range_update_helper(st, right_child(si), mid+1, se, us, ue, nv);

    st[si] = st[left_child(si)] + st[right_child(si)];
}

void update_children(int i, int se, int nv) {
    // if (i >= se) return;
    lazy[left_child(i)] += nv;
    lazy[right_child(i)] += nv;
}

void print_tree(int *st, int arr_size) {
    int h = ceil(log2(arr_size));
    //get the max_size of the segment tree
    int st_size = 2*pow(2, h)-1;
    for (int i=0; i<st_size-1; ++i) {
        printf("%2d ", st[i]);
    }
    printf("%2d\n", st[st_size-1]);
}

int main(int argc, char* argv[]) {
    int arr[] ={ 1, 3, 5, 7, 9, 11 };
    int n = sizeof(arr)/sizeof(arr[0]);

    printf("Size of array: %2d\n", n);

    int *st = buildSegTree(arr, n);
    printf("Before updating range:\n");
    print_tree(st, n);
    printf("sum before update of 1:3 is: %2d\n", sum(st, 1, 3, n));

    lazy_range_update(st, 1, 5, n, 10);
    printf("After updating range:\n");
    print_tree(st, n);
    print_tree(lazy, n);

    printf("sum after update of 1:3 is: %2d\n", sum(st, 1, 3, n));
}