(以“分类:线段树 ==摘要== {{信息题|线段树练习 2|http://www.codevs.cn/problem/1081/|1|100|算法错误|10|time=2015/02/05 14:09:26}} ==题意== 线段...”为内容创建页面) |
小 (→代码: warning) |
||
(未显示1个用户的1个中间版本) | |||
第5行: | 第5行: | ||
线段树操作。 | 线段树操作。 | ||
==题解== | ==题解== | ||
− | *线段树裸题,线段树相关参阅维基百科 http://zh.wikipedia.org/wiki/%E7%BA%BF%E6%AE%B5%E6%A0% | + | *线段树裸题,线段树相关参阅维基百科 http://zh.wikipedia.org/wiki/%E7%BA%BF%E6%AE%B5%E6%A0%91 。 |
+ | |||
==代码== | ==代码== | ||
+ | {{注意|注意|本段代码不适用于成段查询!}} | ||
{{折叠|1081.cpp代码已折叠 | {{折叠|1081.cpp代码已折叠 | ||
|<pre> | |<pre> |
题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因(初次提交分数) |
---|---|---|---|---|---|
线段树练习 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; } |