众所周知，线段树要开四倍，并且传参时还要附带当前节点的 l和r（要么传id），这么写真的不是很优雅啊。。。

1. 性能相关，如果用new去动态开，会不会有毒瘤数据卡不过去？

2. 这样的写法，对于后续的持久化线段树学习会不会有影响？

#include <cstdio>
#include <cstring>
#include <forward_list>
#include <iostream>
#include <numeric>
#include <queue>
using namespace std;
typedef const int cint;
typedef long long ll;

#define lid (id << 1)
#define rid (id << 1 | 1)

cint maxn = 100005;
ll n, t;

ll value[maxn]; // 原数组

struct Node {
	int l, r;
	ll sum;
	Node *left, *right;
	
	void build(ll lnode = 1, ll rnode = n) {
		l = lnode, r = rnode;
		
		if (l == r) {
			sum = value[l];
			return;
		}
		ll mid = (l + r) >> 1; // 区间中点（向下取整）
		
		left = new Node, right = new Node;
		left->build(l, mid);          // 左子树
		right->build(mid + 1, r);     // 右子树
		// 有个性质 有节点就必定有两个子节点 不用担心空指针
		sum = left->sum + right->sum; // 递归求和
	}
	
	// 单点修改
	void modify(ll pos, ll val) {
		if (l == r) {
			sum += val;
			return;
		}
		ll mid = (l + r) >> 1; // 区间中点
		if (pos <= mid)
			left->modify(pos, val);
		else
			right->modify(pos, val);
		
		sum = left->sum + right->sum;
	}
	
	ll query(ll lnode, ll rnode) {
		if (l == lnode && r == rnode)
			return sum;
		ll mid = (l + r) >> 1;
		if (rnode <= mid)
			return left->query(lnode, rnode); // 在左子树 mid包含于左子树
		if (lnode > mid)
			return right->query(lnode, rnode); // 在右子树 mid不包含
		return left->query(lnode, mid) + right->query(mid + 1, rnode); // 从中间砍两半
	}
};

int main() {
	cin >> n;
	if (n == 0)
		return 0;
	for (int i = 1; i <= n; i++) { cin >> value[i]; }
	Node rt;
	rt.build();
	cin >> t;
	while (t--) {
		string op;
		ll a, b;
		cin >> op;
		if (op[0] == 'S') {
			cin >> a >> b;
			cout << rt.query(a, b) << endl;
		} else {
			cin >> a >> b;
			rt.modify(a, b);
		}
	}
	
	return 0;
}