구간 과 (단점 수정, 구간 조회) (선분 트 리)

제목 설명
이것 은 템 플 릿 문제 다.주어진 수열 a [1], a [2], \ dots, a [n], 당신 은 순서대로 q 개의 조작 을 해 야 합 니 다. 조작 은 두 가지 가 있 습 니 다. 1 i x: 주어진 i, x, a [i] 를 x 로 추가 합 니 다.2 l r: 주어진 l, r, 구 \ sum{i = l} ^ ra [i] 의 값 (다시 말 하면 a [l] + a [l + 1] + \ dots + a [r] 의 값 을 구하 십시오).
입력 형식
첫 번 째 줄 은 정수 n, q 2 개 를 포함 하고 수열 길이 와 질문 개 수 를 표시 합 니 다.보증 1 \ \ le n, q \ le 10 ^ 6.두 번 째 줄 n 개의 정수 a [1], a [2], \ dots, a [n] 는 초기 수열 을 나타 낸다.보증 | a [i] | \ le 10 ^ 6.다음 q 줄, 각 줄 의 동작 은 다음 과 같은 두 가지 중 하나 입 니 다. 1 i x: 주어진 i, x, a [i] 에 x 를 추가 합 니 다.2 l r: 주어진 l, r, 구 \ sum{i = l} 의 값 입 니 다.보증 1 \ \ le l \ \ le r \ \ le n, | x | \ \ le 10 ^ 6.
출력 형식
각 2l r 작업 출력 줄 에 대해 서 는 줄 마다 정수 가 있어 서 원 하 는 결 과 를 표시 합 니 다.
본보기
샘플 입력 3, 2, 1, 2, 3, 1, 2, 0, 2, 1, 3 샘플 출력 6
데이터 범위 및 알림
모든 데이터 에 대해 서 는 1 \ \ le n, q \ le 10 ^ 6, | a [i] | \ le 10 ^ 6, 1 \ \ le l \ \ le r \ le n, | x | \ le 10 ^ 6.
사고방식: 선분 트 리 의 템 플 릿 문제 도 트 리 그룹 으로 해결 할 수 있 고 트 리 그룹의 메모리 가 더욱 작다.

#include 
#include 
#include 
#include 
#define ls(x) x << 1 //2 * x
#define rs(x) x << 1 | 1 //2 * x + 1

using namespace std;

typedef long long ll;

const int maxn = 1e6 + 5;

int n, m;
ll a[maxn], ans[4 * maxn], add[4 * maxn]; // 4      ，add   ，ans   

void push_up(int x)
{
	ans[x] = ans[ls(x)] + ans[rs(x)];
}

//    
inline int read()
{
	int s = 0, w = 1;
	char ch = getchar();

	while (ch < '0' || ch > '9')
	{
		if (ch == '-')
			w = -1;
		ch = getchar();
	}

	while (ch >= '0' && ch <= '9')
	{
		s = s * 10 + ch - '0';
		ch = getchar();
	}

	return s * w;
}


//  
void build(int x, int l, int r)
{
	add[x] = 0;
	
	if (l == r)
	{
		ans[x] = a[l];
		return;
	}

	int mid = (l + r) >> 1;

	build(ls(x), l, mid);
	build(rs(x), mid + 1, r);

	push_up(x);
}


//    
void push_down(int x, int l, int r)
{
	int mid = (l + r) >> 1;

	add[ls(x)] += add[x];
	add[rs(x)] += add[x];
	ans[ls(x)] += add[x] * (mid - l + 1);
	ans[rs(x)] += add[x] * (r - mid);
	
	add[x] = 0;
}


//  
void change(int nl, int nr, int l, int r, int x, ll k)
{
	if (nl <= l && r <= nr)
	{
		ans[x] += k * (r - l + 1);
		add[x] += k;
		return;
	}

	push_down(x, l, r);

	int mid = (l + r) >> 1;

	if (nl <= mid)change(nl, nr, l, mid, ls(x), k);
	if (mid + 1 <= nr)change(nl, nr, mid + 1, r, rs(x), k);
	
	push_up(x);
}


//  
ll query(int ql, int qr, int l, int r, int x)
{
	ll res = 0;

	if (ql <= l && r <= qr)return ans[x];

	int mid = (l + r) >> 1;

	push_down(x, l, r);

	if (ql <= mid)res += query(ql, qr, l, mid, ls(x));
	if (mid + 1 <= qr)res += query(ql, qr, mid + 1, r, rs(x));

	return res;
}

int main()
{
	n = read();
	m = read();

	for (int i = 1; i <= n; ++i)
		a[i] = read();

	build(1, 1, n);

	while (m--)
	{
		int judge = read();
		int x = read();
		int y = read();
		ll k;

		if (judge == 1)
			change(x, x, 1, n, 1, y);
		else if (judge == 2)
			printf("%lld
", query(x, y, 1, n, 1));
	}

	return 0;
}