fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 1e5 + 5; 
  12.  
  13. int n, q;  
  14. // int a[N]; 
  15.  
  16. ll seg[4 * N];  
  17.  
  18. // void build(int id, int l, int r) { // O(n)
  19. // 	if (l == r) {
  20. // 		seg[id] = a[l];  
  21. // 		return;
  22. // 	}
  23. // 	int mid = (l + r) >> 1;  
  24. // 	build(id * 2, l, mid); 
  25. // 	build(id * 2 + 1, mid + 1, r);   
  26. // 	seg[id] = seg[id * 2] + seg[id * 2 + 1]; 
  27. // }
  28.  
  29. void update(int id, int l, int r, int pos, int val) { // O(log2(n))
  30. 	// đoạn [l, r] không liên quan gì đến vị trí cần update 
  31. 	if (l > pos || r < pos) return;  
  32.  
  33. 	// đoạn [l, r] chứa pos
  34. 	if (l == r) {
  35. 		seg[id] = val;  
  36. 		return;  
  37. 	}
  38. 	int mid = (l + r) >> 1; 
  39. 	update(id * 2, l, mid, pos, val); 
  40. 	update(id * 2 + 1, mid + 1, r, pos, val);   
  41. 	seg[id] = seg[id * 2] + seg[id * 2 + 1]; 
  42. }
  43.  
  44. ll get(int id, int l, int r, int u, int v) { // O(log2(n))
  45. 	// [l, r] không liên quan gì đến đoạn cần truy vấn [u, v]
  46. 	if (l > v || r < u) return 0;    
  47.  
  48. 	// [l, r] nằm trọn trong [u, v]
  49. 	if (u <= l && r <= v) return seg[id];   
  50.  
  51. 	// [l, r] giao một phần với [u, v]
  52. 	int mid = (l + r) >> 1;  
  53. 	return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v); 
  54. }
  55.  
  56. int main() {
  57. 	ios::sync_with_stdio(false); 
  58. 	cin.tie(nullptr);  	
  59. 	cin >> n >> q; 
  60. 	// for (int i = 1; i <= n; i++) cin >> a[i]; 
  61.  
  62. 	// build(1, 1, n); 
  63.  
  64. 	while (q--) {
  65. 		int type; cin >> type;  
  66.  
  67. 		if (type == 1) {
  68. 			int pos, val; 
  69. 			cin >> pos >> val; 
  70. 			update(1, 1, n, pos, val);  
  71. 		}
  72. 		else {
  73. 			int l, r;  
  74. 			cin >> l >> r; 
  75. 			cout << get(1, 1, n, l, r) << '\n'; 
  76. 		}
  77. 	}
  78. }
  79.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5 8
1 1 2
1 3 5
2 1 3
1 5 4
2 1 5
1 4 3
1 3 5
2 1 4
stdout
copy 
7
11
10
https://ideone.com/T7FRg3
language:
C++14 (gcc 8.3)
created:
39 days 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!