Advertisement
KShah

Untitled

Nov 21st, 2021
65
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //B
  2. #include <vector>
  3. #include <iostream>
  4. #include <cassert>
  5. #include <climits>
  6. // 13 = 8 + 4 + 1 0:00001101 1:00000110 2:00000011 3:00000001 4:00000000
  7. int next_2_degree(int value)
  8. {
  9. int i = 0;
  10. while(value >> i) ++i;
  11.  
  12. return 1 << i;
  13. }
  14.  
  15. //-----------------------------------------------------------------------------
  16.  
  17. class SegmentTree {
  18. public:
  19. SegmentTree(const std::vector<int>& arr, int defaultValue);
  20.  
  21. int Sum(int left, int right) const;
  22. void Update(int val, int pos);
  23. private:
  24. std::vector <int> sum_;
  25. int default_;
  26.  
  27. void build(int index, int left, int right);
  28. void update(int index, int left, int right, int val, int pos);
  29. int sum(int index, int i_left, int i_right, int left, int right) const;
  30. };
  31.  
  32. SegmentTree::SegmentTree (const std::vector<int>& arr, int defaultValue)
  33. : sum_(next_2_degree(arr.size()) * 2, defaultValue),
  34. default_(defaultValue) {
  35.  
  36. std::copy(arr.begin(), arr.end(), sum_.begin() + sum_.size() / 2 - 1);
  37. build(0, 0, sum_.size() / 2 - 1);
  38. }
  39.  
  40. void SegmentTree::build(int index, int left, int right) {
  41. if (left == right) return;
  42.  
  43. const int mid = (left + right) >> 1;
  44. build(2 * index + 1, left, mid);
  45. build(2 * index + 2, mid + 1, right);
  46. sum_[index] = sum_[2 * index + 1] + sum_[2 * index + 2];
  47. }
  48.  
  49. void SegmentTree::Update(int val, int pos) {
  50. if (pos % 2 == 0) {
  51. update(0, 0, sum_.size() / 2 - 1, val, pos);
  52. } else {
  53. update(0, 0, sum_.size() / 2 - 1, (-1 * val), pos);
  54. }
  55. return;
  56. }
  57.  
  58. void SegmentTree::update(int index, int left, int right, int val, int pos) {
  59. if (left == right) {
  60. sum_[index] = val;
  61. return;
  62. }
  63.  
  64. const int mid = (left + right) >> 1;
  65. if (pos <= mid) {
  66. update(2 * index + 1, left, mid, val, pos);
  67. }
  68. if (pos > mid) {
  69. update(2 * index + 2, mid + 1, right, val, pos);
  70. }
  71. sum_[index] = sum_[2 * index + 1] + sum_[2 * index + 2];
  72. }
  73.  
  74. int SegmentTree::Sum(int left, int right) const {
  75. if (left % 2 == 0) {
  76. return sum(0, 0, sum_.size() / 2 - 1, left, right);
  77. } else {
  78. return sum(0, 0, sum_.size() / 2 - 1, left, right) * (-1);
  79. }
  80. }
  81.  
  82. int SegmentTree::sum(int index, int i_left, int i_right, int left, int right) const {
  83. //std::cout << "! " << i_left << " " << i_right << " " << left << " " << right << "\n";
  84. assert(i_left <= i_right && left <= right);
  85.  
  86. if (right < i_left) { return default_; }
  87. if (left > i_right) { return default_; }
  88.  
  89. if (left <= i_left && i_right <= right) {
  90. return sum_[index];
  91. }
  92.  
  93.  
  94. const int mid = (i_left + i_right) / 2;
  95. return sum(2 * index + 1, i_left, mid, left, right) +
  96. sum(2 * index + 2, mid + 1, i_right, left, right);
  97.  
  98. }
  99.  
  100. //-----------------------------------------------------------------------------
  101.  
  102. int main() {
  103. int n;
  104. std::cin >> n;
  105.  
  106. std::vector <int> a(n);
  107. for (int i = 0; i < n; ++i) {
  108. std::cin >> a[i];
  109. if (i % 2 == 1) {
  110. a[i] *= (-1);
  111. }
  112. }
  113. SegmentTree tree(a, 0);
  114.  
  115. int m;
  116. std::cin >> m;
  117. while (m--) {
  118. int k;
  119. int x, y;
  120. std::cin >> k >> x >> y;
  121.  
  122. if (k == 1) {
  123. --x;
  124. --y;
  125. std::cout << tree.Sum(x, y) << "\n";
  126. } else {
  127. --x;
  128. tree.Update(y, x);
  129. }
  130. }
  131. return 0;
  132. }
  133.  
  134.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement