ACM数据结构-线段树

1.维护区间最大最小值模板（以维护最小值为例）

#include<iostream>

#include<stdio.h>

#define LEN 11

#define MAX 1<<30

using namespace std;

int arr[LEN]={,,,,,,,,,,};

int st[LEN*];    //segment tree

int n;

void init(int len){

    n=;

    while(n<len) n*=;    //不断乘以2，知道>=len

    for(int i=;i<n;i++) st[i]=MAX;

}

void update(int p,int v){    //我们有n（len的二次幂扩增）个叶子作为线段元素

    p+=n-;            //地址重定向，变为叶子节点所在地址

    st[p]=v;

    while(p>){

        p=(p-)/;    //向上跳转到父节点

        st[p]=min(st[p*+],st[p*+]);    //更新父节点

    }

}

//    查询［ａ，ｂ）的最小值，当前函数的查询是［ｌ，ｒ） 。当前根节点为ｐ

int query(int a,int b,int p,int l,int r){//外部调用： query(a,b,0,0,n)

    //如果[a,b)与[l,r)不相交

    if(a>=r || b<=l)

        return MAX;

    //如果[a,b)包裹住了[l,r)

    if(a<=l && b>=r)

        return st[p];

    //其他情况，二分进行查询

    int v1=query(a,b,p*+,l,(l+r)/);

    int v2=query(a,b,p*+,(l+r)/,r);

    return min(v1,v2);

}

int main(){

    init(LEN);

    int i,a,b;

    for(i=;i<LEN;i++)

        update(i,arr[i]);

    while(){

        scanf("%d%d",&a,&b);

        printf("%d\n",query(a,b,,,n));

    }

    return ;

} 

---

2.维护区间和的模板

数据结构：

struct node

{

    int left,right;

    int num;

}tree[];

建树：

void build(int left,int right,int index)    //build(1,n,1);

{

    he++;

    tree[index].left=left;

    tree[index].right=right;

    if(left==right)

        return ;

    int mid=(right+left)/;

    build(left,mid,index*);

    build(mid+,right,index*+);

}

单点修改：

void my_plus(int index,int dis,int k)    //将索引为p的元素增加k

{                                        // my_plus(1,p,k)

    tree[index].num+=k;

    if(tree[index].left==tree[index].right)    //没有叶子节点

        return ;

    if(dis<=tree[index*].right)

        my_plus(index*,dis,k);

    if(dis>=tree[index*+].left)

        my_plus(index*+,dis,k);

}

单点查询：

int search(int index,int dis) //调用方法：查找索引为p的元素：search(1,p)

{

    if(tree[index].left==tree[index].right && tree[index].left==dis)

        return tree[index].num;

    if(dis<=tree[index*].right)

        search(index*,dis);

    if(dis>=tree[index*+].left)

        search(index*+,dis);

}

区间修改：

    void pls(int index,int l,int r,int k)

    {

        if(tree[index].left>=l && tree[index].right<=r)

        {

            tree[index].num+=k;

            return ;

        }

        if(tree[index*].right>=l)

           pls(index*,l,r,k);

        if(tree[index*+].left<=r)

           pls(index*+,l,r,k);

    }

区间查询：

void search(int index,int l,int r)

{

    //cout<<index<<" ";

    if(tree[index].left>=l && tree[index].right<=r)

    {

        ans+=tree[index].num;

        return ;

    }

    if(tree[index*].right>=l)

        search(index*,l,r);

    if(tree[index*+].left<=r)

        search(index*+,l,r);

}

---

3.模板编写练习：