세그먼트 트리

#include <bits/stdc++.h>
using ll = long long;
const ll maxv = 101010;
ll arr[maxv];

struct node
{
ll v;
node() : v(0){}
node(ll v) : v(v){}
node operator + (const node& n)
{
return node(n.v + v);
}
} tree[maxv*4];

void init(int s, int e, int n)
{
if (s == e)
{
tree[n] = arr[s];
return;
}
int m = (s + e) >> 1;
init(s, m, n << 1), init(m + 1, e, (n << 1) + 1);
tree[n] = tree[n << 1] + tree[(n << 1) + 1];
}
void update(int s, int e, int n, int idx, int v)
{
if (idx < s || e < idx) return;
if (s == e) { tree[n] = tree[n] + node(v); return; }
int m = (s + e) >> 1;
update(s, m, n << 1, idx, v);
update(m + 1, e, (n << 1) + 1, idx, v);
tree[n] = tree[n << 1] + tree[n << 1 | 1];
}
node query(int s, int e, int n, int l, int r)
{
if (e < l || r < s) return node();
else if (l <= s && e <= r) return tree[n];
int m = (s + e) >> 1;
return query(s, m, n << 1, l, r) + query(m + 1, e, n << 1 | 1, l, r);
}