CodeVS/1081 2015年2月9日 (一) 15:49云璟月（讨论 | 贡献）的版本 (差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

摘要

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

题意

线段树操作。

题解

• 线段树裸题，线段树相关参阅维基百科 http://zh.wikipedia.org/wiki/%E7%BA%BF%E6%AE%B5%E6%A0%91 。

代码

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; }