Fenwick/BIT Tree

fenwick.c

#include <stdlib.h>

typedef struct fenwick_tree{
  int* elems; //stores the elements of the input array
  int *sums; //stores the "sum" of the array at a certain index
} fenwick_tree_t;
//Note sum because it's not a "hard" sum that stretches from index 0 to n, but rather from n's "parent" to n.

//inserts item and updates the sums accordingly
void fenwick_tree_insert(fenwick_tree_t* fenwick_tree, int elem, int i){
  int diff = elem - fenwick_tree->elems[i]; //we need the difference, since we're trying to modify a sum`
  fenwick_tree->elems[i] = elem;
  ++i; //bit operations won't work on 0, since we're using the least signifigant 1 bit.
  while(i) {
    fenwick_tree->sums[i] += diff;
    i -= i & -i; //folks what does this operation do?
  }
}

//gets the sum from 0 to i for the array
int fenwick_tree_sum(fenwick_tree_t* fenwick_tree, int i){
  int sum = 0;
  ++i;
  while(i) {
    sum += fenwick_tree->sums[i];
    i += i & -i; //sum is really a sum of sums organized into a binary tree, hence the name.
  } 
  return sum; //total sum, not sum[i]
}

void init_fenwick_tree(fenwick_tree_t* fenwick_tree, int* elems, int count){
  fenwick_tree->elems = elems;
  //calloc sets elements to zero, why do we use it?
  fenwick_tree->sums = calloc(count + 1, sizeof(int));
  for(int i = 0; i < count; i++)
    fenwick_tree_insert(fenwick_tree, elems[i], i);
}