（以“分类:线段树 ==摘要== {{信息题|线段树练习 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% | + | *线段树裸题，线段树相关参阅维基百科 http://zh.wikipedia.org/wiki/%E7%BA%BF%E6%AE%B5%E6%A0%91 。 |
| + | |||
==代码== | ==代码== | ||
{{折叠|1081.cpp代码已折叠 | {{折叠|1081.cpp代码已折叠 | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 线段树练习 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;
}
|
CloudLunar