使用延迟标记的线段树

自己写的线段树的模板。codepad.org已测试。

使用树形结构存储；动态根据需要建立结点；使用延迟标记更新段；查询时实时计算值。

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

typedef struct _Node{
    int mid; //mid value , can be removed
    int low;
    int high;
    int sign; // value of the segment
    struct _Node* left;
    struct _Node* right;
}Node;
Node* createNode(int low, int high){
    assert(low<=high);

    Node* ret = (Node*)malloc(sizeof(Node));
    ret->mid = ((high+low)>>1);
    ret->low = low;
    ret->high = high;
    ret->sign = 0;
    ret->left = NULL;
    ret->right = NULL;
    return ret;
}

Node* InitialTree(int low, int high){
    assert(low<=high);

    Node* ret = (Node*)malloc(sizeof(Node));
    ret->mid = ((high+low)>>1);
    ret->low = low;
    ret->high = high;
    ret->left = ret->right = NULL;
    ret->sign = 0;
    return ret;
}

void Paint(Node* root, int low, int high){
    low = low<root->low?root->low: low;
    high = high>root->high?root->high: high;
    printf("paint %d %d into segment %d %d \n", low, high, root->low, root->high);
    if(root->low == low && root->high == high){
    //if(root->low == root->high){
        root->sign++;
        printf("value %d-%d = %d\n", root->low, root->high, root->sign);
        return root;
    }

    if(root->left == NULL)
        root->left = createNode(root->low, root->mid);
    if(root->right == NULL)
        root->right = createNode(root->mid+1, root->high);
    if(low <= root->mid)
        Paint(root->left, low, high);
    if(high > root->mid)
        Paint(root->right, low, high);
}
int getValue(Node*root, int position){
    if(position<root->low || position>root->high)
        return -1;
    if(position<=root->mid){
        if(root->left!=NULL)
            return root->sign+getValue(root->left, position);
        return root->sign;
    }
    if(root->right!=NULL)
        return root->sign + getValue(root->right, position);
    return root->sign;
}

int main(){
    Node* root = InitialTree(0,10);
    printf("------------1~5--------------\n");
    Paint(root, 1,5);
    printf("------------2~6--------------\n");
    Paint(root, 2,6);
    printf("------------4~8---------------\n");
    Paint(root, 4,8);
    int i = 0;
    for(;i<=10;i++){
        printf("postion %d = %d \n",i, getValue(root, i));
    }
}