看正月点灯笼老师的笔记—线段树

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define N 1000
int a[N] = { 1,3,5,7,9,11 }, tree[N];
void build_tree(int node, int start, int end)
{
    //printf("%d %d\n", start, end);

    if (start == end)
        tree[node] = a[start];
    else
    {
        int mid = (start + end) / 2;
        int left_node = 2 * node + 1;
        int right_node = 2 * node + 2;

        build_tree(left_node, start, mid);
        build_tree(right_node, mid + 1, end);
        tree[node] = tree[left_node] + tree[right_node];
    }
}
void update_tree(int node, int start, int end,int id,int val)
{
    //printf("%d %d\n", start, end);

    if (start == end)
    {
        a[id] = val; 
        tree[node] = val;
    }
    else
    {
        int mid = (start + end) / 2;
        int left_node = 2 * node + 1;
        int right_node = 2 * node + 2;

        if (id >= start&&id <= mid)
            update_tree(left_node, start, mid, id, val);
        else
            update_tree(right_node, mid + 1, end, id, val);
        tree[node] = tree[left_node] + tree[right_node];
    }
}
int query_tree(int node, int start, int end, int L, int R)
{
    //printf("%d %d\n", start, end);

    if (start > R || end < L)  // 剪枝
        return 0;
    else if (L <= start&&R <= end)   // 剪枝
        return tree[node];
    else if (start == end)
        return tree[node];

    int mid = (start + end) / 2;
    int left_node = 2 * node + 1;
    int right_node = 2 * node + 2;
    int sum_left = query_tree(left_node, start, mid, L, R);
    int sum_right = query_tree(right_node, mid+1, end, L, R);

    return sum_left + sum_right;
}
int main(void)
{
    build_tree(0, 0, 5);
    update_tree(0, 0, 5, 4, 6);


    for (int i = 0; i <= 14; i++)
    {
        printf("%d ", tree[i]);
    }puts("");

    int sum= query_tree(0, 0, 5, 2, 5);

    printf("%d\n", sum);

    system("pause");
    return 0;
}