线段树 (ACM学习笔记)

#include<iostream> typedef long long ll; const int maxn = 1e5 + 5; using namespace std; ll arr[maxn] = { 0 }, tree[5 * maxn] = { 0 }; void build(int node, int start, int end) { //建树 if (start == end) { tree[node] = arr[start]; return; } int leftnode = node * 2; int rightnode = node * 2 + 1; int mid = (start + end) / 2; build(leftnode, start, mid); build(rightnode, mid + 1, end); tree[node] = tree[leftnode] + tree[rightnode]; } void update(int node, int start, int end, int id, int val) { //修改 if (start == end) { tree[node] += val; return; } int leftnode = node * 2; int rightnode = node * 2 + 1; int mid = (start + end) / 2; if (id >= start && id <= mid) update(leftnode, start, mid, id, val); else update(rightnode, mid + 1, end, id, val); tree[node] = tree[leftnode] + tree[rightnode]; } int query(int node, int start, int end, int l, int r) { //查询，l和r是求和的左右区间 if (l <= start && r >= end) return tree[node]; int leftnode = node * 2; int rightnode = node * 2 + 1; int mid = (start + end) / 2; int sum = 0; if (l <= mid) sum += query(leftnode, start, mid, l, r); if (r > mid) sum += query(rightnode, mid + 1, end, l, r); return sum; } int main() { int n; cin >> n; }