fork(3) download
copy 
  1. #pragma pack(1)
  2. #include <iostream>
  3. using namespace std;
  4.  
  5. const int maxn = 1e5;
  6. struct Node { //узел дерева
  7. 	Node *lp, *rp; //дочерние узлы / поддеревья
  8. 	int val; //сумма (или другой параметр) для поддерева
  9. };
  10.  
  11. Node nodes[maxn * 30]; //хранилище узлов, все узлы изначально нулевые (0,null_ptr,null_ptr)
  12. Node* roots[maxn + 1]; 
  13. Node* lastnode = nodes + 1; //первый из свободных узлов
  14.  
  15. int getsum(Node* v, int l, int r, int x, int y) { //найти сумму элементов от x-го до y-го
  16. 	if (v == nullptr) return 0;                   //в поддереве начиная с узла (v,l,r)
  17. 	if(l == x && r == y) {
  18. 		return v -> val;
  19. 	}
  20. 	else {
  21. 		int m = (l + r) / 2;
  22. 		if(y <= m) {
  23. 			return getsum(v -> lp, l, m, x, y);
  24. 		}
  25. 		else if(x > m) {
  26. 			return getsum(v -> rp, m + 1, r, x, y);
  27. 		}
  28. 		else {
  29. 			return getsum(v -> lp, l, m, x, m) + getsum(v -> rp, m + 1, r, m + 1, y);
  30. 		}
  31. 	}
  32. }
  33.  
  34. void update(Node*& v, int l, int r, int pos, int val) { 
  35. 	//обновление элемента с позицией pos в поддереве (v,l,r) (присваивание значения val)
  36. 	//при обновлении всегда создается новый узел
  37. 	Node* old = v; //старый узел (не трогаем!)
  38. 	v = lastnode++; //новый узел из хранилища
  39. 	if(old != nullptr) { // если старый узел существовал
  40. 		*v = *old; //копируем старый узел
  41. 	} //иначе новый узел пуст (0,null_ptr,null_ptr)
  42. 	if(l == r) { //и l==r==pos
  43. 		v -> val = val;
  44. 	}
  45. 	else {
  46. 		int m = (r + l) / 2;
  47. 		if(pos <= m) {
  48. 			update(v -> lp, l, m, pos, val);//обновление левого поддерева
  49. 		}
  50. 		else {
  51. 			update(v -> rp, m + 1, r, pos, val);//обновление правого поддерева
  52. 		}
  53. 		v -> val = 0; //начало пересчета суммы
  54. 		if(v -> lp != nullptr) //если левое поддерево существует
  55. 			v -> val += v -> lp -> val; //учесть его сумму
  56. 		if(v -> rp != nullptr)
  57. 			v -> val += v -> rp -> val;
  58. 	}
  59. }
  60.  
  61. void print(Node* root) {
  62. 	cout << root -> val << " ";
  63. 	if(root -> lp != nullptr) {
  64. 		print(root -> lp);
  65. 	}
  66. 	if(root -> rp != nullptr) {
  67. 		print(root -> rp);
  68. 	}
  69. }
  70.  
  71. int main() {
  72. 	const int N = 1e9;
  73. 	int a[maxn]; //массив
  74. 	int n;
  75. 	cin >> n;
  76. 	for(int i = 1; i <= n; i++) {
  77. 		cin >> a[i];
  78. 	} //ввели с клавиатуры
  79. 	//roots[0] == null_ptr (пустое дерево)
  80. 	for(int i = 1; i <= n; i++) {
  81. 		roots[i] = roots[i - 1]; //новый корень указывает туда же, что и старый
  82. 		update(roots[i], 1, N, i, a[i]); //обновляем дерево с новым корнем,
  83. 		//при этом создается действительно новый корень и некоторые новые узлы
  84. 		//корень имеет диапазон [1,N] и i-тому элементу присваивается значение a[i]
  85. 	}
  86. 	// cout << roots[2] -> val << endl;
  87. 	for(int i = 1; i <= n; i++) {
  88. 		cout << roots[i] -> val << " ";
  89. 	}
  90. 	cout << endl;
  91. 	// print(roots[n]);
  92. 	cout <<getsum(roots[2],1,N,2,3) <<endl; //какая была сумма от 2 до 3 в момент времени 2
  93. 	roots[n+1] = roots[n]; //следующий момент времени n+1
  94. 	update(roots[n+1], 1, N, 2, 0); //обнуляем второй элемент
  95. 	cout <<getsum(roots[n],1,N,1,3) <<endl;
  96. 	cout <<getsum(roots[n+1],1,N,1,3) <<endl;
  97. 	return 0;
  98. }
Success #stdin #stdout 0s 39288KB
comments (?)
stdin
copy 
5
3 5 1 1 1
stdout
copy 
3 8 9 10 11 
5
9
4
https://ideone.com/dQEaHZ
Персистентное дерево отрезков (с комментариями)
language:
C++14 (gcc 8.3)
created:
9 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!