2020-05-28 线段树

//
//  main.cpp
//  数据结构
//
//  Created by Jalor on 2020/5/28.
//  Copyright © 2020 Jalor. All rights reserved.
//

#include <iostream>
#include <cstdio>
using namespace std;

struct Node{//结构体
    int L;
    int R;
    int val = 0;
};

void build_node_tree(int* arr, Node* tree,int node,int start,int end){//建树
    tree[node].L = start;
    tree[node].R = end;
    if (start == end) {
        tree[node].val = arr[start];
        return;
    }
    int mid = (start+end)/2;
    int left_node = node * 2 + 1;
    int right_node = node * 2 +2;
    build_node_tree(arr, tree, left_node, start, mid);
    build_node_tree(arr, tree, right_node, mid+1, end);
    tree[node].val = tree[left_node].val+tree[right_node].val;
}

void update_node_tree(int* arr, Node* tree, int node, int idx, int val){
    int start = tree[node].L;
    int end = tree[node].R;
    int mid = (start+end)/2;
    if (start == end) {
        tree[node].val = val;
        arr[start] = val;
        return;
    }
    int left_node = node * 2 + 1;
    int right_node = node * 2 +2;
    if (idx>=start && idx<=mid) {
        update_node_tree(arr, tree, left_node, idx, val);
    } else {
        update_node_tree(arr, tree, right_node, idx, val);
    }
    tree[node].val = tree[left_node].val+tree[right_node].val;
}

int query_node_tree(int* arr, Node* tree, int node, int L, int R){
    int start = tree[node].L;
    int end = tree[node].R;
    if (R < start || end<L) {
        return 0;
    }
    
    if (L<= start && end<=R) {
        return tree[node].val;
    }
    
    if (start == end) {
        return tree[node].val;
    }
    
    int left_node = node * 2 + 1;
    int right_node = node * 2 +2;
    
    return
    query_node_tree(arr, tree, left_node, L, R)
    + query_node_tree(arr, tree, right_node, L, R);
}

void build_tree(int* arr, int* tree,int node,int start,int end){//建树
    if (start == end) {
        tree[node] = arr[start];
        return;
    }
    int mid = (start+end)/2;
    int left_node = node * 2 + 1;
    int right_node = node * 2 + 2;
    build_tree(arr, tree, left_node, start, mid);
    build_tree(arr, tree, right_node, mid+1, end);
    tree[node] = tree[left_node]+tree[right_node];
}



int main() {
    int num[6]={1,3,5,7,9,11};
    int size = 6;
    int* tree = new int[20];
    Node* node_tree = new Node[20];
    memset(tree, 0, sizeof(int)*20);
    
    build_tree(num,tree,0,0,size-1);
    
    build_node_tree(num,node_tree,0,0,size-1);
    
    update_node_tree(num, node_tree, 0, 4, 6);
    for (int i = 0; i<15; i++) {
        printf("node_tree[%d] = %d\n",i,node_tree[i].val);
    }
    
    int n = query_node_tree(num, node_tree, 0, 0, 5);
    
    printf("%d",n);
    return 0;
}