fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. struct fenwick {
  6. 	ll arr[1000055];
  7. 	void update(int i, ll x) {
  8. 		while (i <= 1000005) {
  9. 			arr[i] += x;
  10. 			i += i & -i;
  11. 		}
  12. 	}
  13. 	ll sum(int i) const {
  14. 		ll x = 0;
  15. 		while (i) {
  16. 			x += arr[i];
  17. 			i -= i & -i;
  18. 		}
  19. 		return x;
  20. 	}
  21. } suma, sumb;
  22.  
  23. int main() {
  24. 	int q;
  25. 	scanf("%d", &q);
  26. 	while (q--) {
  27. 		int t, l, r;
  28. 		scanf("%d %d %d", &t, &l, &r);
  29. 		if (t == 1) {
  30. 			int x;
  31. 			scanf("%d", &x);
  32. 			suma.update(l, x); suma.update(r + 1, -x);
  33. 			sumb.update(l, (1ll - l) * x); sumb.update(r + 1, 1ll * r * x);
  34. 		}
  35. 		else {
  36. 			ll ans = 0;
  37. 			ans += suma.sum(r) * r + sumb.sum(r);
  38. 			ans -= suma.sum(l - 1) * (l - 1) + sumb.sum(l - 1);
  39. 			printf("%lld\n", ans);
  40. 		}
  41. 	}
  42. 	return 0;
  43. }
Success #stdin #stdout 0s 30856KB
comments (?)
stdin
copy 
8
1 1 3 5
2 2 4
1 2 4 3
2 2 4
1 2 3 9
2 2 4
1 2 2 -7
2 2 4
stdout
copy 
10
19
37
30
https://ideone.com/T0sOTc
range update and range sum : BIT solution
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!