线段树

#include<iostream>
#include<vector>
#include<cstring>
#include<cassert>
using namespace std;
template <typename E>
class SegmentTree{
private:
    E *tree;
    E *data;
    int size;

    //建立线段树
    void buildSegmentTree(int treeIndex,int l,int r){
        if(l==r){
            tree[treeIndex]=data[l];
            return ;
        }
        int leftIndex=leftChild(treeIndex);
        int rightIndex=rightChild(treeIndex);

        int mid=l+(r-l)/2;
        buildSegmentTree(leftIndex,l,mid);
        buildSegmentTree(rightIndex,mid+1,r);
        tree[treeIndex]=tree[leftIndex]+tree[rightIndex];
    }

    //左孩子节点索引
    int leftChild(int index){
        return  index*2+1;
    }

    //右孩子节点索引
    int rightChild(int index){
        return index*2+2;
    }

    //查询queryl到queryr线段元素的和
    E  query(int treeIndex,int l,int r,int queryl,int queryr){

        if(l==queryl&&r==queryr)
            return tree[treeIndex];
        int mid=l+(r-l)/2;
        int leftIndex=leftChild(treeIndex);
        int rightIndex=rightChild(treeIndex);
        if(queryl>=mid+1)
            return query(rightIndex,mid+1,r,queryl,queryr);
        else if(queryr<=mid)
            return query(leftIndex,l,mid,queryl,queryr);

        E leftresult=query(leftIndex,l,mid,queryl,mid);
        E rightresult=query(rightIndex,mid+1,r,mid+1,queryr);

        return leftresult+rightresult;

    }

    void set(int treeIndex,int l,int r,int index,E e){
        if(l==r)
            tree[treeIndex]=e;
        int mid=l+(r-l)/2;
        int leftIndex=leftChild(treeIndex);
        int righIndex=rightChild(treeIndex);
        if(mid<index)
            set(righIndex,mid+1,r,index,e);
        if(mid>=index)
            set(leftIndex,l,mid,index,e);
        tree[treeIndex]=tree[leftIndex]+tree[righIndex];
    }
public:
    SegmentTree(E arr[],int n){
        this->data=new E[n];
        for(int i=0;i<n;i++)
            data[i]=arr[i];
        this->tree=new E[4*n];
        this->size=n;
        buildSegmentTree(0,0,n-1);
    }

    int getSize(){
        return this->size;
    }

    E get(int index){
        if(index<0||index>=size){
            cout<<"Error"<<endl;
            return NULL;
        }
        return data[index];
    }

    E query(int queryl,int queryr){
        if(queryl<0||queryl>=size||queryr<0||queryr>=size){
            cout<<"Error"<<endl;
            return NULL;
        }
        return query(0,0,size-1,queryl,queryr);
    }

    void set(int index,E e){
        if(index<0||index>=size){
            cout<<"Error"<<endl;
            return ;
        }
        data[index]=e;
        set(0,0,size-1,index,e);
    }
};