세그트리

ll arr[1000002];
ll tree[4 * 1000002];
ll N, M, K;
ll order;
ll a, b, c, d;

ll init(ll start, ll end, ll node)
{
	if (start == end)
		return tree[node] = arr[start];

	ll mid = (start + end) / 2;

	return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}

ll query(ll start, ll end, ll node, ll left, ll right)
{
	if (left > end || right < start)
		return 0;

	if (left <= start && end <= right)
		return tree[node];

	ll mid = (start + end) / 2;

	return query(start, mid, node * 2, left, right) + query(mid + 1, end, node * 2 + 1, left, right);
}

ll update(ll start, ll end, ll node, ll index, ll diff)
{
	if (index < start || end < index)
		return tree[node];

	if (start == end)
		return tree[node] = diff;;

	ll mid = (start + end) / 2;

	return tree[node] = update(start, mid, node * 2, index, diff) + update(mid + 1, end, node * 2 + 1, index, diff);
}