백준 11659 구간 합 구하기 4

#include <iostream>
#include <vector>

using namespace std;

int N, M, from, to;
int arr[100001];

void update(vector<int> &tree, int target, int diff);
int sum(vector<int>& tree, int target);

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	vector<int> tree(N + 1);
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
		update(tree, i + 1, arr[i]);
	}
	for (int i = 0; i < M; i++)
	{
		cin >> from >> to;
		cout << sum(tree, to) - sum(tree, from - 1)<<'\n';
	}
	/*for (int i = 0; i < M; i++)
	{
		int sum = 0;
		cin >> from >> to;
		for (int j = from; j <= to; j++)
		{
			sum += arr[j - 1];
		}
		cout << sum << '\n';
	}*/

	return 0;
}

void update(vector<int>& tree, int target, int diff)
{
	while (target < tree.size())
	{
		tree[target] += diff;
		target += (target & -target);
	}
}
int sum(vector<int>& tree, int target)
{
	int ans = 0;
	while (target > 0)
	{
		ans += tree[target];
		target -= (target & -target);
	}
	return ans;
}