线段树基本操作练习

#include<iostream>

using namespace std;

const int MAXLEN = 100;
int len = 6;
int arr[] = { 1,3,5,7,9,11 };
int tree[MAXLEN] = { 0 };

void build_tree(int s, int e, int node);
void update_tree(int s, int e, int node, int idx, int value);
int  query_tree(int l,int r,int s,int e,int node);
int  query2_tree(int l, int r, int s, int e, int node);

int main() {
    build_tree(0, len - 1, 0);
    for (int i = 0; i < 15; i++) cout << tree[i]<<" ";
    cout << endl;
    update_tree(0, len - 1, 0, 4, 6);
    for (int i = 0; i < 15; i++) cout << tree[i] << " ";
    cout << endl;
    int sum = query_tree(2, 5, 0, len - 1, 0);
    cout<< sum;
}

//递归出口为无交集时返回0，包含时，返回值为当前区间的和
int query2_tree(int l, int r, int s, int e, int node) {
    if (r<s || l>e)return 0;
    if (s>=l && e<=r) return tree[node];
    int mid = (s + e) / 2;
    return  query2_tree(l, r, s, mid, node * 2 + 1) + query2_tree(l, r, mid + 1, e, node * 2 + 2);
}

//s arr的开始下标，e arr的结束下标，node树当前遍历的结点,查询arr数组从l开始到r结束的数字的和。
int query_tree(int l,int r,int s, int e, int node) {
    if (l == s && r == e)return tree[node];
    int mid = (s+e)/2;
    if (l > mid)
        return query_tree(l, r, mid + 1, e, node * 2 + 2);
    else if (r <= mid) 
        return query_tree(l, r, s, mid, node * 2 + 1);
    else {
        return query_tree(l, mid, s, mid, node * 2 + 1) + query_tree(mid + 1, r, mid + 1, e, node * 2 + 2);
    }
}

//s arr的开始下标，e arr的结束下标，node树当前遍历的结点，idx修改数组的索引，修改数组索引的值。
void update_tree(int s, int e, int node, int idx, int value) {
    if (s == e) {
        arr[idx] = value;
        tree[node] = value;
        return;
    }
    int mid = (s + e) / 2;
    if (idx <= mid) update_tree(s, mid, node * 2 + 1, idx, value); else
        update_tree(mid+1,e,node*2+2,idx,value);
    tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2];
}

//s arr的开始下标，e arr的结束下标，node树当前遍历的结点
void build_tree(int s, int e, int node) {
    if (s == e) {
        tree[node] = arr[s];
    }
    else {
        build_tree(s, (s + e) / 2, node * 2 + 1);
        build_tree((s + e) / 2 + 1, e, node * 2 + 2);
        tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2];
    }
}