zkw线段树存档

#include <iostream>
#include <cstdio>
#include <cmath>
#define int long long
using namespace std;
int sum[2197157];
int a[1000005];
int size, depth;
int query(int); int query(int, int);
void build(){//给出最后一层，O(n)建树 
	for(int i = size; i; i--){
		sum[i] = sum[i * 2] + sum[i * 2 + 1];
	}
}
void modify(int idx, int val){//O(logn)单点加 
	for(sum[idx += size] += val, idx >>= 1; idx; idx >>= 1){
		sum[idx] = sum[idx * 2] + sum[idx * 2 + 1];
	}
}
int query(int l, int r){//O(logn)区间加 
	int ct = 0;
	for(l = l + size - 1, r = r + size + 1; l ^ r ^ 1; l >>= 1, r >>= 1){
		if(~l & 1) ct += sum[l ^ 1];
		if(r & 1) ct += sum[r ^ 1];
	}
	return ct;
}
char *p1, *p2, buf[(1 << 25)];
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 25, stdin), p1 == p2)? EOF : *p1++)
int read(){//快读
	char c = getchar();
	int x = 0, f = 1;
	while(!isdigit(c)){
		if(c == '-') f = -f;
		c = getchar();
	}
	while(isdigit(c)){
		x = (x << 3) + (x << 1) + c - '0';
		c = getchar();
	}
	return x * f;
}
void _write(int n){//快写
	if(n == 0) return;
	_write(n / 10);
	putchar(n % 10 + '0');
}
void write(int n, bool end = 0){//快写，增加了输出0和负数并附带换行
    if(n < 0) putchar('-'), _write(-n);
    else if(n == 0) putchar('0');
    else _write(n);
    putchar('\n');
}
signed main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	int n = read(), m = read();
	size = 1 << (depth = ceil(log2(n)) + 1e-5);
	for(int i = 1; i <= n; i++){
		sum[i + size] = a[i] = read();
	}
	build();
	while(m--){
		int tmp = read(), l = read(), r = read();
		if(tmp == 1) modify(l, r);
		else write(query(l, r));
	}

	return 0;
}