Persistent BIT

Persistent_BIT.cpp

// Update O(log(N))
// Query O(Log^2(N))
//Problema de teste : https://tinyurl.com/y95bucb5

#include <bits/stdc++.h>
#define N 100050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int T, n, q, v[N], a, b, c, d, id;

vector < pii > bit[N];

inline void update(int x, int v)
{
	for(int i = x; i < N; i += (i&-i))
	{
		if(bit[i].empty()) bit[i].push_back({id, v});

		else bit[i].push_back({id, bit[i].back().s + v}); 
	}
}

inline int query(int x, int id)
{
	int sum = 0;

	for(int i = x; i > 0; i -= (i&-i))
	{
		int ini = 0, fim = bit[i].size() - 1, mid, best = -1;

		while(fim >= ini)
		{
			mid = (ini + fim)/2;

			if(bit[i][mid].f <= id) best = mid, ini = mid + 1;

			else fim = mid - 1;
		}

		if(best != -1) sum += bit[i][best].s;
	}

	return sum;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>T;

	while(T--)
	{
		for(int i = 0; i < N; i++) bit[i].clear();

		id = 0;

		cin>>n;

		for(int i = 1; i <= n; i++)
		{
			cin>>v[i];

			update(i, v[i]);
		}

		cin>>q;

		while(q --)
		{
			cin>>a>>b>>c;

			if(a == 1) // QUERY ENTRE (b, c) APÓS "d" ATUALIZAÇÕES
			{
				cin>>d;

				cout<<query(c, d) - query(b - 1, d)<<"\n";
			}

			else // ATUALIZAÇÃO NA POSIÇÃO " b "
			{
				++id;

				update(b, c - v[b]);

				v[b] = c;
			}
		}
	}
}

interessante

realmente interessante