果的线段树，需要用到lazy-tag的方法，朴素果断超时
朴素线段树
#include <stdio.h>
const int N= 105100;
struct Node
{
int left, right;
__int64 sum, add;
}node[4*N];
int num, n, q;
__int64 data[N];
char str[1];
void swap(int &a, int &b)
{
int t= a;
a= b;
b= t;
}
void build_tree(int left, int right, int p)
{
node[p].left=left;
node[p].right=right;
node[p].add=0;
if ( left < right )
{
int mid= left+right>>1;
build_tree(left, mid, 2*p);
build_tree(mid+1, right, 2*p+1);
node[p].sum= node[2*p].sum+node[2*p+1].sum;
}
else if ( left == right )
node[p].sum= data[left];
}
void update(int p)
{
node[p<<1].sum+= node[p].add*(node[p<<1].right-node[p<<1].left+1);
node[(p<<1)+1].sum+= node[p].add*(node[(p<<1)+1].right-node[(p<<1)+1].left+1);
node[p<<1].add+= node[p].add;
node[(p<<1)+1].add+= node[p].add;
node[p].add= 0;
}
__int64 query(int s, int t, int p)
{
__int64 sum= 0, i= 0, j= 0;
if ( s <= node[p].left && node[p].right <= t)
return node[p].sum;
if ( node[p].add)
update(p);
int mid= node[p].right+node[p].left>>1;
if ( s <= mid )
i = query(s, t, p<<1);
if ( t > mid )
j = query(s, t, (p<<1)+1);
return i+j;
}
void adds(int s, int t, __int64 add, int p)
{
if ( s <= node[p].left && node[p].right <= t)
{
node[p].add+=add;
node[p].sum+=add*(node[p].right-node[p].left+1);
return;
}
if ( node[p].add)
update(p);
int mid= node[p].right+node[p].left>>1;
if ( s <= mid )
adds( s, t, add, p<<1);
if ( t > mid )
adds( s, t, add, (p<<1)+1);
node[p].sum= node[p<<1].sum+node[(p<<1)+1].sum;
}
int main()
{
scanf("%d%d", &n, &q);
int i, left, right;
__int64 value;
data[0]= 0;
for ( i = 1 ; i <= n ; i++ )
scanf("%I64d", data+i);
build_tree(1, n, 1);
while ( q-- )
{
scanf("%s", str);
if ( 'Q' == str[0] )
{
scanf("%d%d", &left, &right);
printf("%I64d\n", query(left, right, 1));
}
else
{
scanf("%d%d%I64d", &left, &right, &value);
if ( left > right )
swap(left, right);
if ( value )
adds(left, right, value, 1);
}
}
return 0;
}
zkw线段树
#include <stdio.h>
const int N= 105100;
struct Node
{
int left, right;
__int64 sum, add;
}node[4*N];
int num, n, q;
__int64 data[N];
char str[10];
void build_tree()
{
int i;
for ( i = 2*num-1 ; i >= num ; i-- )
{
if ( i-num > n)
node[i].sum= 0;
else
node[i].sum= data[i-num];
node[i].left= node[i].right= i-num;
node[i].add= 0;
}
while ( i > 0 )
{
node[i].sum=node[i<<1].sum+node[(i<<1)+1].sum;
node[i].left= node[i<<1].left;
node[i].right= node[(i<<1)+1].right;
node[i].add= 0;
i--;
}
}
__int64 query(int s, int t)
{
__int64 sum= 0;
int num_s= 0, num_t= 0;
for ( s= s+num-1, t= t+num+1 ; s^t^1 ; s>>=1, t>>=1 )
{
if (~s&1)
{
sum+=node[s^1].sum;
num_s+= node[s^1].right-node[s^1].left+1;
}
if ( t&1 )
{
sum+=node[t^1].sum;
num_t+= node[t^1].right-node[t^1].left+1;
}
sum+=node[s>>1].add*num_s;
sum+=node[t>>1].add*num_t;
}
for (s>>=1 ; s > 0 ; s>>=1 )
sum+=node[s].add*(num_s+num_t);
return sum;
}
void add(int s, int t, __int64 d)
{
int num_s= 0, num_t= 0;
for ( s= s+num-1, t= t+num+1 ; s^t^1 ; s>>=1, t>>=1 )
{
if (~s&1)
{
node[s^1].add+= d;
node[s^1].sum+=(node[s^1].right-node[s^1].left+1)*d;
num_s+= node[s^1].right-node[s^1].left+1;
}
if ( t&1 )
{
node[t^1].add+= d;
node[t^1].sum+=(node[t^1].right-node[t^1].left+1)*d;
num_t+= node[t^1].right-node[t^1].left+1;
}
node[s>>1].sum+=d*num_s;
node[t>>1].sum+=d*num_t;
}
for (s>>=1 ; s > 0 ; s>>=1 )
node[s].sum+=d*(num_s+num_t);
}
int main()
{
scanf("%d%d", &n, &q);
int i, left, right;
__int64 value;
data[0]= 0;
for ( i = 1 ; i <= n ; i++ )
scanf("%I64d", data+i);
for ( num = 1 ; num < (n+2) ; num<<=1 );
build_tree();
while ( q-- )
{
scanf("%s", str);
if ( 'Q' == str[0] )
{
scanf("%d%d", &left, &right);
printf("%I64d\n", query(left, right));
}
else
{
scanf("%d%d%I64d", &left, &right, &value);
if ( value )
add(left, right, value);
}
}
return 0;
}