2
\$\begingroup\$

Here is my implementation of a segment tree with a sample driver file (I didn't make an update function because I didn't need it for what I was doing).

I'm a huge fan of geeksforgeeks, but I do not understand why this link makes such a complicated implementation. I didn't use the height or compute the maximum size in order to build mine. Not to mention, their structure really isn't a tree; it's an integer array.

I'm looking for what I implemented well and what I did not implement well.

#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;
}
\$\endgroup\$
5
  • 5
    \$\begingroup\$ Hi. Welcome to Code Review! What problem is this code supposed to solve? What is a "segment tree" and why do you expect it to help? That may be explained in the link but should be included here in case of link rot. As stands, this sort of reads as you asking why the code in the link works a certain, which would be off-topic as asking for an explanation of someone else's code. \$\endgroup\$
    – mdfst13
    Jun 24 '16 at 3:28
  • \$\begingroup\$ Their tree is "An integer array" because it's faster than using the linked node approach you're using. They don't have to deference multiple pointers, only recursively search the array. \$\endgroup\$
    – Benjamin
    Jun 24 '16 at 5:32
  • \$\begingroup\$ @mdfst13 This is an attempt to solve the problem of sums over a given range in O(nlogn) as opposed to O(n). For example, if you have an integer array of some very large number and wanted to know the sum between 0-8000, the query would take you O(logn)...so you'd find the element with twelve memory accesses as opposed to 8000. \$\endgroup\$
    – MrPickles
    Jun 24 '16 at 12:37
  • 1
    \$\begingroup\$ What aspects of reviewing do you want? What is the goal here? \$\endgroup\$ Jun 25 '16 at 3:21
  • \$\begingroup\$ @chux Mainly if this is valid implementation of a segment tree or not. My driver file seems to lead me to believe it is, but I'm not sure if I missed anything (not already mentioned in my OP). \$\endgroup\$
    – MrPickles
    Jun 25 '16 at 3:28
2
\$\begingroup\$

Bounds checking simplification

Your bounds checking code is overly complicated. This total overlap check:

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

could be reduced to:

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

In this partial overlap check:

/* Partial overlap */
if((start >= node->start && start <= node->end) ||
       (end >= node->end && end <= node->start) ||
       (start <= node->start && end >= node->start))

I noticed that the second of the three conditions always evaluates to false. Some of the other parts are also unnecessary. In fact the whole thing could be rewritten as:

/* Partial overlap */
if (start <= node->end && end >= node->start)

Use of globals

The function build_tree() references the array ra directly. It would be better for that array to be passed in as an argument. Otherwise that function can't be used for any other segment tree.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.