建树

void build(int o,int l,int r)   //o:当前建立的节点 l:左端点  r:右端点{    if(l == r)                  //建立叶子信息        st[o] = a[l];    else    {        int m = l + ((r-l) >> 1);   // m 为中间点，左儿子结点为 [l,m] ，右儿子结点为 [m+1,r]；        build(o << 1,l,m);          //构建左儿子结点        build((o<<1)|1,m+1,r);      //构建右儿子结点        st[o] = max(st[o << 1],st[(o<<1)|1]);   //递归返回时用儿子结点更新父节点，此处可进行更新最大值、最小值、区间和等操作    }} build(1, 1, n);//主函数里的语句

 

 单点修改

void update(int o,int l,int r,int ind,int ans)  //o、l、r为当前更新到的结点、左右端点，ind为需要修改的叶子结点左端点，ans为需要修改成的值；{    if(l == r)      //若当前更新点的左右端点相等即到叶子结点时，直接更新信息并返回    {        st[o] = ans;        return ;    }    int m = l + ((r-l) >> 1);    if(ind <= m)        update(o << 1,l,m,ind,ans);    else        update((o<<1)|1,m+1,r,ind,ans);    st[o] = max(st[o<<1],st[(o<<1)|1]);     //递归回之后用儿子结点更新父节点（此处是区间最大值）也可以是最小值或者是区间和} update(1, 1, n, a, b);//在主函数里的语句

 

区间查询

int query(int o,int l,int r,int ql,int qr)      //ql、qr为需要查询的区间左右端点{    if(ql > r || qr < l)    //若当前结点和需要查找的区间不相交，则返回一个对于区间查询无关的值（如求和时返回0，求最大值时返回-1等）        return -1;    if(ql <=l && qr >=r)    //若当前结点的区间被需要查询的区间覆盖，则返回当前结点的信息        return st[o];    int m = l + ((r-l) >> 1);    int p1 = query(o<<1,l,m,ql,qr);     //p1为查询左儿子结点得到的信息，p2为查询右儿子结点得到的信息    int p2 = query((o<<1)|1,m+1,r,ql,qr);    return max(p1,p2);      //综合两个儿子结点的信息并返回}query(1, 1, n, a, b)//主函数里的查询语句

 

然后是线段数的区间修改以及相应的查询：

区间修改用到了lazy的思想，即当一个区间需要更新时，只递归更新到那一层结点，并将其下层结点所需要更新的信息保存在数组中，然后返回，只有当下次遍历到那个结点（更新过程中或查询过程中），才将那个结点的修改信息传递下去，这样就避免了区间修改的每个值的修改

区间修改（包括区间加值和区间赋值）及相应查询：

区间加值：

void pushup(int o){　　　　　　　　　　//pushup函数，该函数本身是将当前结点用左右子节点的信息更新，此处求区间和，用于update中将结点信息传递完返回后更新父节点    st[o]=st[o<<1]+st[o<<1|1];}  void pushdown(int o,int l,int r){　　//pushdown函数，将o结点的信息传递到左右子节点上    if(add[o]){　　　　　　　　　　　　　//当父节点有更新信息时才向下传递信息        add[o<<1]+=add[o];　　　　　　//左右儿子结点均加上父节点的更新值        add[o<<1|1]+=add[o];        int m=l+((r-l)>>1);        st[o<<1]+=add[o]*(m-l+1);　　//左右儿子结点均按照需要加的值总和更新结点信息        st[o<<1|1]+=add[o]*(r-m);        add[o]=0;　　　　　　　　　　　　　　　　//信息传递完之后就可以将父节点的更新信息删除    }} void update(int o,int l,int r,int ql,int qr,int addv){　　//ql、qr为需要更新的区间左右端点，addv为需要增加的值    if(ql<=l&&qr>=r){　　　　　　　　　　　　　　　　　　　　　　//与单点更新一样，当当前结点被需要更新的区间覆盖时        add[o]+=addv;　　　　　　　　　　　　　　　　　　　　　　//更新该结点的所需更新信息        st[o]+=addv*(r-l+1);　　　　　　　　　　　　　　　　//更新该结点信息        return;　　　　　　　　　　　　　　　　　　　　//根据lazy思想，由于不需要遍历到下层结点，因此不需要继续向下更新，直接返回    }        pushdown(o,l,r);　　　　　　　　　　　　　　　　　　//将当前结点的所需更新信息传递到下一层（其左右儿子结点）    int m=l+((r-l)>>1);    if(ql<=m)update(o<<1,l,m,ql,qr,addv);　　　　　//当需更新区间在当前结点的左儿子结点内，则更新左儿子结点    if(qr>=m+1)update(o<<1|1,m+1,r,ql,qr,addv);　　　//当需更新区间在当前结点的右儿子结点内，则更新右儿子结点    pushup(o);　　　　　　　　　　　　　　　　　　//递归回上层时一步一步更新回父节点}ll query(int o,int l,int r,int ql,int qr){　　　　//ql、qr为需要查询的区间    if(ql<=l&&qr>=r) return st[o];　　　　　　//若当前结点覆盖区间即为需要查询的区间，则直接返回当前结点的信息    pushdown(o,l,r);　　　　　　　　　　　　　　　　　　//将当前结点的更新信息传递给其左右子节点    int m=l+((r-l)>>1);    ll ans=0;　　　　　　　　　　　　　　　　　　　　　　//所需查询的结果    if(ql<=m)ans+=query(o<<1,l,m,ql,qr);　　　　　//若所需查询的区间与当前结点的左子节点有交集，则结果加上查询其左子节点的结果    if(qr>=m+1)ans+=query(o<<1|1,m+1,r,ql,qr);　//若所需查询的区间与当前结点的右子节点有交集，则结果加上查询其右子节点的结果　　 return ans; }

 区间改值（其实只有pushdown函数和update中修改部分与区间加值不同）：

void pushup(int o){     st[o]=st[o<<1]+st[o<<1|1]; }  void pushdown(int o,int l,int r){　　//pushdown和区间加值不同，改值时修改结点信息只需要对修改后的信息求和即可，不用加上原信息     if(change[o]){         int c=change[o];         change[o<<1]=c;         change[o<<1|1]=c;         int m=l+((r-l)>>1);         st[o<<1]=(m-l+1)*c;         st[o<<1|1]=(r-m)*c;         change[o]=0;     } }  void update(int o,int l,int r,int ql,int qr,int c){     if(ql<=l&&qr>=r){　　　　　　　　　//同样更新结点信息和区间加值不同         change[o]=c;         st[o]=(r-l+1)*c;         return;     }          pushdown(o,l,r);     int m=l+((r-l)>>1);     if(ql<=m)update(o<<1,l,m,ql,qr,c);     if(qr>=m+1)update(o<<1|1,m+1,r,ql,qr,c);     pushup(o); }  int query(int o,int l,int r,int ql,int qr){     if(ql<=l&&qr>=r) return st[o];     pushdown(o,l,r);     int m=l+((r-l)>>1);     int ans=0;     if(ql<=m)ans+=query(o<<1,l,m,ql,qr);     if(qr>=m+1)ans+=query(o<<1|1,m+1,r,ql,qr);     return ans; }