Advertisement
KShah

Untitled

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