查看CodeVS/1081的源代码 ←CodeVS/1081

[[分类:线段树]]
==摘要==
{{信息题|线段树练习 2|http://www.codevs.cn/problem/1081/|1|100|算法错误|10|time=2015/02/05 14:09:26}}
==题意==
线段树操作。
==题解==
*线段树裸题，线段树相关参阅维基百科 http://zh.wikipedia.org/wiki/%E7%BA%BF%E6%AE%B5%E6%A0%91 。

==代码==
{{注意|注意|本段代码不适用于成段查询!}}
{{折叠|1081.cpp代码已折叠
|<pre>
#include<cstdio>
template<size_t N>
class SegmentTree
{
    //模板：线段树//
public:
    int tree[N];
    int lazy[N];
    #define cm int m=(l+r)>>1
    #define lp p<<1
    #define rp p<<1|1
    #define lc lp,l,m
    #define rc rp,m+1,r
    #define stdp int p,int l,int r
    int build(stdp)
    {
        if(l==r)
        {
            scanf("%d",&tree[p]);
            return tree[p];
        }
        cm;
        return tree[p]=build(lc)+build(rc);
    } 
    void update(int L,int R,int delta,stdp)
    {
        if(L<=l&&r<=R)
        {
            lazy[p]+=delta;
            return;
        }
        cm;
        if(L<=m)update(L,R,delta,lc);
        if(R>m)update(L,R,delta,rc);
    }
    int query(int L,int R,stdp)
    {
        if(L<=l&&r<=R) return tree[p]+lazy[p];
        int ret=lazy[p];
        cm;
        if(L<=m)ret+=query(L,R,lc);
        if(R>m)ret+=query(L,R,rc);
        return ret;
    }
};
SegmentTree<2000000> st;
int main()
{
    int n;
    scanf("%d",&n);
    st.build(1,1,n);
    int Q,f,a,b,d;
    scanf("%d",&Q);
    while(Q--)
    {
        int f;
        scanf("%d",&f);
        if(f==1)
        {
            scanf("%d%d%d",&a,&b,&d);
            st.update(a,b,d,1,1,n);
        }
        else
        {
            int a;
            scanf("%d",&a);
            printf("%d\n",st.query(a,a,1,1,n));
        }
    }
    return 0;
}
</pre>
|code1081}}