线段树(结构体)模板
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<map>
#include<cmath>
#include<string>
using namespace std;
typedef long long ll;
int ans;
struct node
{
int l, r, w;
int f;
};
struct node tree[50000 * 4 + 1];
void BuildSegmentTree(int k, int l, int r) // 建线段树
{
tree[k].l = l;
tree[k].r = r;
if(l == r)
{
scanf("%lld", &tree[k].w);
return ;
}
int m = (tree[k].l + tree[k].r) >> 1;
BuildSegmentTree(k << 1, l, m);
BuildSegmentTree(k << 1 | 1, m + 1, r);
tree[k].w = tree[k << 1].w + tree[k << 1 | 1].w;
}
void down(int k) // 懒标记
{
tree[k << 1].f += tree[k].f;
tree[k << 1 | 1].f += tree[k].f;
tree[k << 1]. w += tree[k].f * (tree[k << 1].r - tree[k <<1].l + 1);
tree[k << 1 |1].w += tree[k].f * (tree[k << 1| 1].r - tree[k << 1| 1].l + 1);
tree[k].f = 0;
}
void Single_Point_Modification(int k, int x, int y) // 单点修改
{
if(tree[k].l == tree[k].r)
{
tree[k].w += y;
return ;
}
int m = (tree[k].l + tree[k].r) >> 1;
if(x <= m) Single_Point_Modification(k << 1,x, y);
else Single_Point_Modification(k << 1 | 1, x, y);
tree[k].w = tree[k << 1].w + tree[k << 1 | 1]. w;
}
void Single_Point_Query(int k, int x) // 单点查询
{
if(tree[k].l == tree[k].r)
{
ans = tree[k].w;
return ;
}
if(tree[k].f) down(k);
int m = (tree[k].l + tree[k].r) >> 1;
if(x <= m) Single_Point_Query(k << 1, x);
else Single_Point_Query(k << 1 | 1, x);
}
void Interval_modification(int k, int x, int y,int z) //区间修改
{
if(tree[k].l >= x && tree[k].r <= y)
{
tree[k].w += (tree[k].r - tree[k].l + 1) * z;
tree[k].f += z;
return;
}
if(tree[k].f) down(k);
int m = (tree[k].l + tree[k].r) >> 1;
if(x <= m) Interval_modification(k << 1, x, y, z);
if(y > m) Interval_modification(k << 1 | 1, x, y, z);
tree[k].w = tree[k << 1].w + tree[k << 1 | 1].w;
}
void Interval_Query(int k, int x, int y) //区间查询
{
if(tree[k].l >= x && tree[k].r <= y)
{
ans += tree[k].w;
return ;
}
if(tree[k].f) down(k);
int m = (tree[k].l + tree[k].r) / 2;
if(x <= m) Interval_Query(k << 1, x, y);
if(y > m) Interval_Query(k << 1 | 1, x, y);
}
char s[10];
int main()
{
int T, n;
while(~scanf("%d",&T))
{
int cas = 0;
while(T--)
{
scanf("%d", &n);
BuildSegmentTree(1,1,n);
printf("Case %d:\n",++ cas);
while(1)
{
int x, y, z;
getchar();
scanf("%s",s);
if(s[0] == 'E')break;
else if(s[0]== 'A') // 区间修改
{
scanf("%d %d %d", &x, &y, &z);
Interval_modification(1,x,y,z);
}
else if(s[0] =='B') // 区间查询
{
ans = 0;
scanf("%d %d", &x, &y);
Interval_Query(1, x, y);
printf("%d\n",ans);
}
else if(s[0]=='C') // 单点修改
{
scanf("%d %d", &x, &y);
Single_Point_Modification(1,x,y);
}
else if(s[0]=='D') // 单点查询
{
ans = 0;
scanf("%d", &x);
Single_Point_Query(1,x);
printf("%d\n",ans);
}
}
}
}
return 0;
}