以下是我今天解题的题解报告:
[1]区间求和
题目描述
给定一数列,规定有两种操作,一是修改某个元素,二是求区间的连续和。
输入
输入数据第一行包含两个正整数n,m(n<=100000,m<=500000),以下是m行,
输出
每行有三个正整数k,a,b(k=0或1, a,b<=n).k=0时表示将a处数字加上b,k=1时表示询问区间[a,b]内所有数的和。对于每个询问输出对应的答案。
样例输入
10 20
0 1 10
1 1 4
0 6 6
1 4 10
1 8 9
1 4 9
0 10 2
1 1 8
0 2 10
1 3 9
0 7 8
0 3 10
0 1 1
1 3 8
1 6 9
0 5 5
1 1 8
0 4 2
1 2 8
0 1 1
样例输出
10
6
0
6
16
6
24
14
50
41
思路:
这题是一个模板题, 因为最开始没有赋值,初始为0,一共n个点,先build线段树,
操作为0,就把第x个数加上y,
操作为1,就输出区间[x,y]的总和

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
const int maxn = 1e5+10;
ll sum[maxn*4];

void build(int l,int r,int rt)
{
	sum[rt] = 0;
	if(l == r)
		return ;
	int mid = (l+r)/2;
	build(l,mid,2*rt);
	build(mid+1,r,2*rt+1);
	sum[rt] = sum[2*rt] + sum[2*rt+1];
}

void update(int x,int y,int l,int r,int rt)
{
	if(l == r)
	{
		sum[rt] += y;
		return ; 
	}
	int mid = (l+r)/2;
	if(x <= mid) update(x,y,l,mid,2*rt);
	else update(x,y,mid+1,r,2*rt+1);
	
	sum[rt] = sum[2*rt] + sum[2*rt+1];
}

ll query(int x,int y,int l, int r,int rt)
{
	if(x <= l && r <= y)
	{
		return sum[rt];
	}
	ll ans = 0;
	int mid = (r+l)/2;
	if(x <= mid)
	{
		ans += query(x,y,l,mid,2*rt);
	}
	if(y>mid)
	{
		ans += query(x,y,mid+1,r,2*rt+1);
	}
	return ans;
	
}

int main(){
	int n,m;
   while(~scanf("%d %d", &n, &m))
	{
		build(1,n,1);
		while(m--)
		{
			int k,a,b;
			scanf("%d %d %d",&k,&a,&b);
			if(k == 0)
			{
				update(a,b,1,n,1);
			}
			else
			{
				printf("%lld\n",query(a,b,1,n,1));
			}
		}
	}
	return 0;
}

[2]一个简单的整数问题
题目描述
你有N个整数,A1,A2,…,AN。 你需要处理两种操作。 一种操作是在给定间隔中为每个数字添加一些给定数字。 另一种是要求给定间隔中的数字总和。
输入
第一行包含两个数字N和Q.1≤N,Q≤100000。
第二行包含N个数字,A1,A2,…,AN的初始值。 -1000000000≤AI≤1000000000。
接下来的Q行中的每一行代表一个操作。
“C a b c”表示将C添加到Aa,Aa + 1,…,Ab中的每一个。 -10000≤c≤10000。
“Q a b”表示查询Aa,Aa + 1,…,Ab的总和。
输出
你需要回到Q个询问,每个询问一行。

样例输入
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
样例输出
4
55
9
15
提示
总和可能超过32位整数的范围。
思路:
这道题是区间更新,如果每次都到叶子节点去加上更新的值,会时间超限,
可以用lazy标记,存在lazy标记代表这个区间被修改了,下一次再修改或者查询到这个区间时,把下面两个子区间更新(pushdown操作),此时这个节点上的lazy标记=0


#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
const int maxn = 1e5+10;
ll sum[maxn*4];
ll lazy[maxn*4];

char s[10];
ll a[maxn];

void pushup(int rt)
{
	sum[rt] = sum[2*rt] + sum[2*rt+1]; 
}

void pushdown(int rt,int len)
{
	if(lazy[rt] != 0)
	{
		lazy[2*rt] += lazy[rt];
		lazy[2*rt+1] += lazy[rt];
		sum[2*rt] += (len-len/2) * lazy[rt];
		sum[2*rt+1] += (len/2) * lazy[rt];
		lazy[rt] = 0;
	}
}

void build(int l,int r,int rt)
{
	lazy[rt] = 0;
	if(l == r)
	{
		sum[rt] = a[l];
		return ;	
	}
	int mid = (l+r)/2;
	build(l,mid,2*rt);
	build(mid+1,r,2*rt+1);
	pushup(rt);
}

void update(int x,int y,int l,int r,int rt,ll c)
{
	if(x <= l && r <= y)
	{
		lazy[rt] += c;
		sum[rt] += (r-l+1)*c;
		return ; 
	}
	pushdown(rt,r-l+1);
	int mid = (l+r)/2;
	if(x <= mid)
		update(x,y,l,mid,2*rt,c);
	if(y > mid)
		update(x,y,mid+1,r,2*rt+1,c);
	pushup(rt);
}

ll query(int x,int y,int l, int r,int rt)
{
	if(x <= l && r <= y)
	{
		return sum[rt];
	}
	pushdown(rt,r-l+1);
	ll ans = 0;
	int mid = (r+l)/2;
	if(x <= mid)
	{
		ans += query(x,y,l,mid,2*rt);
	}
	if(y > mid)
	{
		ans += query(x,y,mid+1,r,2*rt+1);
	}
	return ans;
	
}

int main(){
	int N,Q;
   while(~scanf("%d %d", &N, &Q))
	{
		for(int i = 1 ; i <= N; i++)
		{
			scanf("%lld",&a[i]);
		}
		build(1,N,1);
		while(Q--)
		{
			int l,r;
			ll x;
			scanf("%s %d %d",s,&l,&r);
			if(s[0] == 'Q')
			{
				printf("%lld\n",query(l,r,1,N,1));
			} 
			else
			{
				scanf("%lld",&x);
				update(l,r,1,N,1,x);
			}
		}
	}
	return 0;
}