1112 - Curious Robin Hood

1112 - Curious Robin Hood

Topic: BIT

	//Space Complexity: O(N)
	// Time Complexity: O(NlogN)
	#include<bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define MAX 100005
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int BIT[MAX], n;
	//int a[MAX];
	//int a[MAX] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
	void print()
	{
	for(int i = 1; i <= n; i++){
	cerr << BIT[i] << " ";
	}
	cerr << "\n";
	cerr << "------------\n";
	}
	void update(int x, int val)
	{
	for(; x <= n; x += x & (-x)){
	BIT[x] += val;
	}
	}
	int query(int x)
	{
	int sum = 0;
	for(; x > 0; x -= x & (-x))
	sum += BIT[x];
	return sum;
	}
	int main()
	{
	//FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int T;
	scanf("%d", &T);
	for(int cs = 1; cs <= T; cs++){
	int q;
	scanf("%d %d", &n, &q);
	for(int i = 0; i <= n; i++){
	BIT[i] = 0;
	// a[i] = 0;
	}
	for(int i = 1; i <= n; i++)
	{
	// scanf("%d", &a[i]);
	int x;
	scanf("%d",&x);
	update(i, x);
	}
	// print();
	printf("Case %d:\n", cs);
	while(q--){
	int x;
	scanf("%d", &x);
	if(x == 1){
	int i;
	scanf("%d", &i);
	int t = (query(i+1) - query(i));
	//a[i+1] = 0;
	printf("%d\n", t);
	//print();
	update(i+1, -t);
	//print();
	}
	else if(x == 2){
	int i,v;
	scanf("%d %d", &i, &v);
	//a[i+1] += v;
	update(i+1, v);
	}
	else{
	int i,j;
	scanf("%d %d", &i, &j);
	int ans = (query(j+1) - query(i));
	printf("%d\n",ans);
	}
	}
	}
	// printf("sum of first 10 elements is %d\n", (query(10)) );
	//printf("sum of all elements in range [2, 7] is %d\n", (query(7) - query(2 - 1)) );
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw 1112(Loj).cpp hosted with ❤ by GitHub

Share: