线段树模板-白红宇

线段树模板

阅读量：5338 次

发布时间：2019-06-15

本文共 1779 字，大约阅读时间需要 5 分钟。

#define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1const int maxn = 55555;int sum[maxn<<2];void PushUP(int rt) {         sum[rt] = sum[rt<<1] + sum[rt<<1|1];}void build(int l,int r,int rt) {         if (l == r) {                 scanf("%d",&sum[rt]);                 return ;         }         int m = (l + r) >> 1;         build(lson);         build(rson);         PushUP(rt);}void update(int p,int add,int l,int r,int rt) {         if (l == r) {                 sum[rt] += add;                 return ;         }         int m = (l + r) >> 1;         if (p <= m) update(p , add , lson);         else update(p , add , rson);         PushUP(rt);}int query(int L,int R,int l,int r,int rt) {         if (L <= l && r <= R) {                 return sum[rt];         }         int m = (l + r) >> 1;         int ret = 0;         if (L <= m) ret += query(L , R , lson);         if (R > m) ret += query(L , R , rson);         return ret;}

线段树单点修改，区间求和

#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1const int maxn=200005;int Max[maxn<<2];void PushUP(int rt){    Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);}void build(int l,int r,int rt){    if(l==r)    {        scanf("%d",&Max[rt]);        return ;    }    int m=(l+r)>>1;    build(lson);    build(rson);    PushUP(rt);}void update(int p,int sc,int l,int r,int rt){    if(l==r){        Max[rt]=sc;        return ;    }    int m=(l+r)>>1;    if(p<=m){        update(p,sc,lson);    }    else update(p,sc,rson);     PushUP(rt);}int query(int L,int R,int l,int r,int rt){   if(L<=l&&r<=R)        return Max[rt];    int ret=0;    int m=(l+r)>>1;   if(L<=m) ret=max(ret,query(L,R,lson));   if(R>m)  ret=max(ret,query(L,R,rson));   return ret;}

线段树单点更行，区间更新极值

线段树数组要开到4倍节点的原因：

推荐线段树博客：

转载于:https://www.cnblogs.com/zhgyki/p/9911947.html

你可能感兴趣的文章