segpersi.cpp

#include <bits/stdc++.h>
using namespace std;

#define MID ((l + r)/2)

struct node
{
	node *left, *right;

	int sum;

	node()
	{
		left = right = nullptr;
		sum = 0;
	}
};

void update(node* anterior, node* atual, int pos, int val, int l, int r)
{
	if(l == r)
	{
		atual->sum = val;
		return;
	}

	int mid = (l + r)/2;

	if(anterior->right == nullptr) anterior->right = new node();
	if(anterior->left == nullptr) anterior->left = new node();

	if(pos <= mid)
	{
		atual->right = anterior->right;

		atual->left = new node();

		update(anterior->left, atual->left, pos, val, l, mid);
	}
	else
	{
		atual->left = anterior->left;

		atual->right = new node();

		update(anterior->right, atual->right, pos, val, mid + 1, r);
	}

	atual->sum = atual->left->sum + atual->right->sum;
}

int query(node* atual, int a, int b, int l, int r)
{
	if(l >= a and r <= b) return atual->sum;

	if(l > b or r < a) return 0;

	int mid = (l + r)/2;

	int esquerda = query(atual->left, a, b, l, mid);
	int direita = query(atual->right, a, b, mid + 1, r);

	return esquerda + direita;
}

int main()
{

}