题目意思很简单,有N个数,Q个操作, Q l r 表示查询从l到r 的和,C l r v 表示将从l到r 的值加上v,明显的线段树,不知道线段树的人肯定暴力,肯定超时,哈哈!!
解题方法我在代码注释中写的很详细了
#include <stdio.h>
const int maxn = 100005;
typedef __int64 ll; //Hint The sums may exceed the range of 32-bit integers.
int a[maxn];
struct node //比较复杂的线段树都需要保存一个节点的多个信息,虽然
{ //可以使用多个数组来存储,但我个人不推荐这种做法
int l, r, m;
ll sum, mark;
}tree[maxn<<2]; // << 这里使用位运算,位运算的效率要比* /运算的效率高
//推荐大家在乘除2或2的某次方的时候使用位运算,
void build(int l, int r, int o) //建树比较好理解,确定每个节点的各项,然后递归创建左右子树
{
tree[o].l = l;
tree[o].r = r;
int m = (l+r)>>1;
tree[o].m = m;
tree[o].mark = 0; //mark的值一定要初始化为0,很重要
if (l == r) //递归边界
{
tree[o].sum = a[l];
return;
}
build(l, m, o<<1);
build(m+1, r, (o<<1)+1);
tree[o].sum = tree[o<<1].sum + tree[(o<<1)+1].sum; //这里tree[(o<<1)+1] (o<<1) 我打了括号,以为位运算的优先级比+低
} //不注意很容易出问题的
void update(int l, int r, int v, int o)
{
if (tree[o].l == l && tree[o].r == r)
{
tree[o].mark += v; //在每次更新某段的时候我们还要我们标记这一段被加了v
return;
}
tree[o].sum += (ll)(r-l+1)*v;
if (tree[o].m >= r) //递归更新,无外乎三种情况
update(l, r, v, o<<1);
else if (l > tree[o].m)
update(l, r, v, (o<<1)+1);
else
{
update(l, tree[o].m, v, o<<1);
update(tree[o].m+1, r, v, (o<<1)+1);
}
}
ll query(int l, int r, int o)
{
if (tree[o].l == l && tree[o].r == r) //我们也使用递归的方式查询,这是递归边界
return tree[o].sum + tree[o].mark*(r-l+1);
if (tree[o].mark != 0)
{
tree[o<<1].mark += tree[o].mark; //在查询的时候我将节点的mark值传递给子节点
tree[(o<<1)+1].mark += tree[o].mark;
tree[o].sum += (ll)(tree[o].r -tree[o].l +1)*tree[o].mark; //并更新sum的值
tree[o].mark = 0;
}
if (tree[o].m >= r) //查询的三种情况
return query(l, r, o<<1);
else if (tree[o].m <l)
return query(l, r, (o<<1)+1);
else
return query(l, tree[o].m, o<<1) + query(tree[o].m+1, r, (o<<1)+1);
}
int main()
{
int n, q;
while (scanf("%d%d",&n,&q) != EOF)
{
for(int i = 1; i <= n; i++)
scanf("%d",&a[i]);
build(1, n, 1);
char com;
int l, r, v;
while (q--)
{
getchar();
scanf("%c",&com);
if (com == 'Q')
{
scanf("%d%d",&l, &r);
printf("%I64d\n",query(l,r,1));
}
else
{
scanf("%d%d%d",&l ,&r ,&v);
update(l, r, v, 1);
}
}
}
return 0;
}