[数据结构与算法]P3368 【模板】树状数组2

【模板】树状数组 2 - 洛谷https://www.luogu.com.cn/problem/P3368

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <cmath>
#include <map>
#include <cstdlib>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MN = 65005;
const int MAXN = 2000010;
const int INF = 0x3f3f3f3f;
#define IOS ios::sync_with_stdio(false)

int n, m;
struct node {
	int l, r;
	ll sum, num = 0;
} tree[2 * MAXN];
int s[MAXN];

inline void build(int i, int l, int r) {
	tree[i].l = l;
	tree[i].r = r;
	if (tree[i].l == tree[i].r) {
		tree[i].sum = s[l];
		return ;
	}
	int mid = l + r >> 1;
	build(i * 2, l, mid);
	build(i * 2 + 1, mid + 1, r);
	tree[i].sum = tree[i * 2].sum + tree[i * 2 + 1].sum;
}

ll search(int i, int l, int r) {
	if (tree[i].l >= l && tree[i].r <= r) {
		return tree[i].sum;
	}
	if (tree[i].r < l || tree[i].l > r) {
		return 0;
	}
	ll v = 0;
	if (tree[i * 2].r >= l) {
		v += search(i * 2, l, r);
	}
	if (tree[i * 2].l <= r) {
		v += search(i * 2 + 1, l, r);
	}
	return v;
}

inline void add(int i, int dis, int k) {
	if (tree[i].l == tree[i].r) {
		tree[i].sum += k;
		return;
	}
	if (dis <= tree[i * 2].r) {
		add(i * 2, dis, k);
	} else {
		add(i * 2 + 1, dis, k);
	}
	tree[i].sum = tree[i * 2].sum + tree[i * 2 + 1].sum;
}
ll ans = 0;

inline void query(int i, int dis) {
	ans += tree[i].num;
	if (tree[i].l == tree[i].r) {
		//printf("%lld\n", tree[i].sum);
		ans += tree[i].sum;
		return ;
	}
	if (tree[i * 2].r >= dis) {
		query(i * 2, dis);
	} else {
		query(i * 2 + 1, dis);
	}
}

inline void add_sec(int i, int l, int r, int k) {
	if (tree[i].l >= l && tree[i].r <= r) {
		tree[i].num += k;
		return ;
	}
	if (tree[i * 2].r >= l) {
		add_sec(i * 2, l, r, k);
	}
	if (tree[i * 2 + 1].l <= r) {
		add_sec(i * 2 + 1, l, r, k);
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", s + i);
	}
	build(1, 1, n);
	int t, x, y, k;
	while (m--) {
		scanf("%d", &t);
		if (t == 1) {
			scanf("%d %d %d", &x, &y, &k);
			add_sec(1, x, y, k);
		} else if (t == 2) {
			scanf("%d", &x);
			query(1, x);
			printf("%lld\n", ans);
			ans = 0;
		}
	}
	return 0;
}