线段树

poj 2182
二叉树实现

#include<stdio.h>
const int maxn=1e4;
struct {
    int l,r,len;
}tree[maxn*4];//结构数组
int pre[maxn],ans[maxn];
void Buildtree(int left,int right,int u){
    tree[u].l=left;
    tree[u].r=right;
    tree[u].len=right-left+1;//更新结点的值
    if(left==right)
        return;
    Buildtree(left,(left+right)>>1,u<<1);//递归左子树
    Buildtree(((left+right)>>1)+1,right,(u<<1)+1);//递归右子树
}
int query(int u,int num){//查询+维护，所求值为当前区间左起第num个元素
    tree[u].len--;//对访问到的区间维护len,即把这个结点上元素的数量减一
    if(tree[u].l == tree[u].r) return tree[u].l;
    //左子区间元素的个数不够，则查询右子区间中左起的第num-tree[u<<1].len个元数
    if(tree[u<<1].len<num) 
       return query((u<<1)+1,num-tree[u<<1].len);
    //左子区间元素足够，则继续查询左区间左起第num个元素
    else
        return query(u<<1,num);
}
int main(){
   int n,i;
   scanf("%d",&n);
   pre[1]=0;
   for(i=2;i<=n;i++) scanf("%d",&pre[i]);
   Buildtree(1,n,1);
   for( i=n;i>=1;i--) ans[i]=query(1,pre[i]+1);
   for( i=1;i<=n;i++) printf("%d\n",ans[i]);
   return 0;
}

完全二叉树实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include <vector>
#include<map>
#include<set>
#include<utility>
using namespace std;
typedef long long ll;
const ll INF = -1e9;
const ll N =8e3+7;
const ll mod=1e9+7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;b >>= 1;a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
ll getinv(ll x){return qpow(x,mod-2,mod);}
int n;
int ans[N],pre[N],tree[N*4];
void BuildTree(int n,int last_left){//完全二叉树构建线段树
    for(int i=last_left;i<last_left+n;i++){//给完全二叉树最后一行赋值，左边n个结点是n头牛
        tree[i]=1;
    }
    while(last_left!=1){//从二叉树的最后一行倒推到根结点，根结点的值是牛的总数
        for(int i=last_left/2;i<last_left;i++){
            tree[i]=tree[i*2]+tree[i*2+1];
        }
        last_left=last_left/2;
    }
}
int query(int u,int num,int last_left){
    //查询+维护，关键一点是所求的值为当前区间左起第num个元素
    tree[u]--;//对访问到的区间维护剩下的牛的个数
    if(tree[u]==0&&u>=last_left)
    return u;
    //左子区间的数字个数不够，则查询右子区间左起第num-tree[u<<1]个元素的个数
    if(tree[u<<1]<num)
         return query((u<<1)+1,num-tree[u<<1],last_left);
    //左区间的数字个数足够，依旧查询左子区间左起第num个元素
    if(tree[u<<1]>=num)
         return query(u<<1,num,last_left);
    return 0;
}
int main(){
    n=read();
    int last_left=1<<(int(log(double(n))/log(double(2))+1));
    pre[1]=0;
    for(int i=2;i<=n;i++) pre[i]=read();
    BuildTree(n,last_left);
    for(int i=n;i>=1;i--){
        ans[i]=query(1,pre[i]+1,last_left)-last_left+1;
    }
    for(int i=1;i<=n;i++){
        printf("%d\n",ans[i]);
    }
}

poj3468
区间求和以及区间加法

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include <vector>
#include<map>
#include<set>
#include<utility>
using namespace std;
typedef long long ll;
const ll INF = -1e9;
const ll N =1e5+1;
const ll mod=1e9+7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;b >>= 1;a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
ll getinv(ll x){return qpow(x,mod-2,mod);}
ll sum[N<<2],add[N<<2];//sum表示该点区间的总和,add记录区间是否用到lazy
void push_up(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void push_down(int rt,int m){
    if(add[rt]){
        add[rt<<1]+=add[rt];
        add[rt<<1|1]+=add[rt];
        sum[rt<<1]+=(m-(m>>1))*add[rt];
        sum[rt<<1|1]+=(m>>1)*add[rt];
        add[rt]=0;//取消本层标记
    }
}
void build(int l,int r,int rt){//l,r是区间的左右端点，rt是编号,满二叉树建树
    add[rt]=0;
    if(l==r){//叶子结点，赋值
        scanf("%lld",&sum[rt]);
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    push_up(rt);
}
void update(int a,int b,ll c,int l,int r,int rt){//区间更新
    if(a<=l&&b>=r){//区间刚好是要更新的区间的子区间
        sum[rt]+=(r-l+1)*c;
        add[rt]+=c;//用到了lazy-tag
        return;//不用向下继续深入
    }
    push_down(rt,r-l+1);//向下更新
    int mid=(l+r)>>1;
    if(a<=mid) update(a,b,c,l,mid,rt<<1);//左搜
    if(b>mid) update(a,b,c,mid+1,r,rt<<1|1);
    push_up(rt);//往上更新
}
ll query(int a,int b,int l,int r,int rt){//区间求和
    if(a<=l&&b>=r) return sum[rt];//满足lazy，直接返回sum
    push_down(rt,r-l+1);//向下更新
    int mid=(l+r)>>1;
    ll ans=0;
    if(a<=mid) ans+=query(a,b,l,mid,rt<<1);
    if(b>=mid+1) ans+=query(a,b,mid+1,r,rt<<1|1);
    return ans;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    build(1,n,1);
    while(m--){
        char q;
        int a,b;
        ll c;
        scanf(" %c",&q);
        if(q=='C'){
            scanf("%d%d%lld",&a,&b,&c);
            update(a,b,c,1,n,1);
        }
        else{
            scanf("%d%d",&a,&b);
            printf("%lld\n",query(a,b,1,n,1));
        }
    }
}

hdu1166

区间查询以及点修改

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include <vector>
#include<map>
#include<set>
#include<utility>
using namespace std;
typedef long long ll;
const ll INF = -1e9;
const ll N =5e4+7;
const ll mod=1e9+7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;b >>= 1;a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
ll getinv(ll x){return qpow(x,mod-2,mod);}
ll sum[N<<2],add[N<<2];//sum表示该点区间的总和,add记录区间是否用到lazy
void build(int l,int r,int rt){//l,r是区间的左右端点，rt是编号,满二叉树建树
    add[rt]=0;
    if(l==r){//叶子结点，赋值
        scanf("%lld",&sum[rt]);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void Add(int i,int j,int l,int r,int rt){//单点更新
    sum[rt]+=j;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(i<=mid) Add(i,j,l,mid,rt<<1);//左搜
    if(i>mid) Add(i,j,mid+1,r,rt<<1|1);
}
ll query(int a,int b,int l,int r,int rt){//区间求和
    if(a<=l&&b>=r) return sum[rt];
    int mid=(l+r)>>1;
    ll ans=0;
    if(a<=mid) ans+=query(a,b,l,mid,rt<<1);
    if(b>mid) ans+=query(a,b,mid+1,r,rt<<1|1);
    return ans;
}
int main(){
    int t,n,j=0;
    scanf("%d",&t);
    while(t--){
        cout<<"Case "<<++j<<":\n";
        scanf("%d",&n);
        build(1,n,1);
        string q;int i,j;
        while(1){
            cin>>q;
            if(q=="End") break;
            scanf("%d%d",&i,&j);
            if(q=="Add"){
                Add(i,j,1,n,1);
            }
            else if(q=="Query"){ 
                printf("%lld\n",query(i,j,1,n,1));
            }
            else if(q=="Sub"){
                Add(i,-j,1,n,1);
            }
        }
    }
    return 0;   
}

小阳的贝壳

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = -1e9;
const ll N =1e5+7;
const ll mod=1e9+7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;b >>= 1;a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
ll getinv(ll x){return qpow(x,mod-2,mod);}
ll sum[N<<2],a[N],d[N<<2],gcd[N<<2];
int n,m;
void push_up(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    gcd[rt]=__gcd(gcd[rt<<1|1],gcd[rt<<1]);
    d[rt]=max(d[rt<<1],d[rt<<1|1]);
}
void build(int l,int r,int rt){//l,r是区间的左右端点，rt是编号,满二叉树建树
    if(l==r){//叶子结点，赋值
        gcd[rt]=d[rt]=abs(sum[rt]=a[l]);
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    push_up(rt);
}
void update(int pos,int val,int l,int r,int rt){
    if(l==r){
        a[l]+=val;
        gcd[rt]=d[rt]=abs(sum[rt]=a[l]);
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) update(pos,val,l,mid,rt<<1);//左搜
    if(pos>mid) update(pos,val,mid+1,r,rt<<1|1);
    push_up(rt);//往上更新
}//单点修改
int qsum(int a,int b,int l,int r,int rt){//区间求和
    if(a<=l&&b>=r) return sum[rt];
    int mid=(l+r)>>1;
    ll ans=0;
    if(a<=mid) ans+=qsum(a,b,l,mid,rt<<1);
    if(b>=mid+1) ans+=qsum(a,b,mid+1,r,rt<<1|1);
    return ans;
}
int query(int a,int b,int type,int l,int r,int rt){
    if(a<=l&&b>=r) return type?d[rt]:gcd[rt];
    int mid=l+r>>1,ans=0;
    if(a<=mid) ans+=query(a,b,type,l,mid,rt<<1);
    if(b>mid) {
        int res=query(a,b,type,mid+1,r,rt<<1|1);
        if(type) ans=max(ans,res);
        else ans=__gcd(ans,res);
    }
    return ans;
}//0求相邻元素最大公约数，1求相邻元素的最大差
int main(){
   cin>>n>>m;
   for(int i=1;i<=n;i++) a[i]=read();
   for(int i=n;i;i--)  a[i]-=a[i-1];
   build(1,n,1);
   for(int i=1;i<=m;i++){
       int op,l,x,r;
       cin>>op;
       if(op==1){
           cin>>l>>r>>x;
           update(l,x,1,n,1);
           if(r<n) update(r+1,-x,1,n,1);
           continue;
       }
       if(op==2){
           cin>>l>>r;
           cout<<query(l+1,r,1,1,n,1)<<endl;
           continue;
       }
       if(op==3){
           cin>>l>>r;
           cout<<__gcd(qsum(1,l,1,n,1),query(l+1,r,0,1,n,1))<<endl;//gcd(a[l],)
       }
   }
   return 0;
}