(以“分类:线段树 ==摘要== {{信息题|线段树练习 2|http://www.codevs.cn/problem/1081/|1|100|算法错误|10|time=2015/02/05 14:09:26}} ==题意== 线段...”为内容创建页面)
 
题解: 链接
第5行: 第5行:
 
线段树操作。
 
线段树操作。
 
==题解==
 
==题解==
*线段树裸题,线段树相关参阅维基百科 http://zh.wikipedia.org/wiki/%E7%BA%BF%E6%AE%B5%E6%A0%91。
+
*线段树裸题,线段树相关参阅维基百科 http://zh.wikipedia.org/wiki/%E7%BA%BF%E6%AE%B5%E6%A0%91 。
 +
 
 
==代码==
 
==代码==
 
{{折叠|1081.cpp代码已折叠
 
{{折叠|1081.cpp代码已折叠

2015年2月9日 (一) 15:49的版本

摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因(初次提交分数)
线段树练习 2 ★☆☆☆☆ 答案正确 100 2015/02/05 14:09:26 算法错误(10)

题意

线段树操作。

题解

代码

1081.cpp代码已折叠
展开折叠内容
#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;
}

著作权声明[编辑]

关于[编辑]