问分段树挑战

EN

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

typedef struct segment_tree_node_s
{
  struct segment_tree_node_s * left;
  struct segment_tree_node_s * right;
  int start;
  int end;
  int sum;
} segment_tree_node_t;

typedef struct segment_tree_s
{
  segment_tree_node_t * root;
} segment_tree_t;

int build_tree(segment_tree_node_t **, int, int);
int query_tree(segment_tree_node_t *, int, int);

static const int ra[] = {1,3,5,7,9,11};
int main(int argc, char * argv[])
{
  segment_tree_t * new_tree = (segment_tree_t *) malloc(sizeof(segment_tree_t));
  int length = sizeof(ra)/sizeof(ra[0]);
  int sum = build_tree(&new_tree->root, 0, length - 1);
  int sum_2 = query_tree(new_tree->root, 0, 0); 
  int sum_3 = query_tree(new_tree->root, 0, 1); 
  int sum_4 = query_tree(new_tree->root, 0, 2); 
  int sum_5 = query_tree(new_tree->root, 0, 3); 
  int sum_6 = query_tree(new_tree->root, 0, 4); 
  int sum_7 = query_tree(new_tree->root, 1, 5); 
  int sum_8 = query_tree(new_tree->root, 2, 4); 
  int sum_9 = query_tree(new_tree->root, 4, 5); 
  int sum_10 = query_tree(new_tree->root, 5, 5); 

  printf("Sum of tree [0-5]: %d\n", sum);
  printf("Sum of tree [0-0]: %d\n", sum_2);
  printf("Sum of tree [0-1]: %d\n", sum_3);
  printf("Sum of tree [0-2]: %d\n", sum_4);
  printf("Sum of tree [0-3]: %d\n", sum_5);
  printf("Sum of tree [0-4]: %d\n", sum_6);
  printf("Sum of tree [1-5]: %d\n", sum_7);
  printf("Sum of tree [2-4]: %d\n", sum_8);
  printf("Sum of tree [4-5]: %d\n", sum_9);
  printf("Sum of tree [5-5]: %d\n", sum_10);

  return 0;
}

int build_tree(segment_tree_node_t ** node, int start, int end)
{
  *node = (segment_tree_node_t *)malloc(sizeof(segment_tree_node_t));
  (*node)->sum = 0;

  if(start != end)
  {
    (*node)->start = start;
    (*node)->end   = end;
    int mid = start + (end - start)/2;
    return (*node)->sum = build_tree(&((*node)->left), start, mid) + build_tree(&((*node)->right), mid + 1, end);   
  }
  else
  {
    (*node)->start = start;
    (*node)->end   = end;
    (*node)->sum = ra[start];
    return ra[start];
  }
}

int query_tree(segment_tree_node_t * node, int start, int end)
{
    /* Total overlap */
    if(node->start >= start && node->start <= end)
    {
        if(node->end <= end && node->end >= start)
            return node->sum;
    }

    /* Partial overlap */
    if((start >= node->start && start <= node->end) || (end >= node->end && end <= node->start) || (start <= node->start && end >= node->start))
            return query_tree(node->left, start, end) + query_tree(node->right, start, end);

    /* No overlap */
    return 0;
}