线段树，从入门到放弃

线段树用来解决符合结合律的区间求极值，区间求和，求区间最大公约数等类似问题

线段树作为一种工具，可以将区间修改维护的时间从O(N)降到O(logN)

1.线段树求区间和的简单入门

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define ls(k) (k)<<1
#define rs(k) (k)<<1|1
/**
定义线段树结构
sum
l
r
lazytag 
**/
struct node{
    int l; //区间左端点 
    int r; //区间右端点 
    int sum; //区间和 
    int lazy;//懒标记    
}tree[MAXN*4]; 

int a[MAXN];

//开始建树 
void buildTree(int i,int l,int r){
    tree[i].l=l;
    tree[i].r=r;
    //到达叶子节点
    if(tree[i].l==tree[i].r){
        tree[i].sum=a[l];
        return;
    }
    int mid=(l+r)>>1;
    buildTree(ls(i),l,mid);
    buildTree(rs(i),mid+1,r);
    tree[i].sum=tree[ls(i)].sum+tree[rs(i)].sum; 
}

//查询区间和 
int query(int i,int l,int r){
    if(tree[i].l==l&&tree[i].r==r){
        return tree[i].sum;
    }
    //往左边找 
    if(tree[ls(i)].r>=r){
        return query(ls(i),l,r); 
    }
    //往右边找 
    else if(tree[rs(i)].l<=l){
        return query(rs(i),l,r);
    }
    else{
        //有交集 
        return query(ls(i),l,tree[ls(i)].r)+query(rs(i),tree[rs(i)].l,r);
    } 
    
}
 
 
int main(){
    
    int n=10;
    for(int i=1;i<=n;i++){
        a[i]=i;
    }
    buildTree(1,1,10);
    int res=query(1,1,10);
    printf("%d",res);
    return 0;
}