Advertisement
Guest User

Untitled

a guest
Feb 25th, 2020
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.41 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <algorithm>
  4. #include <functional>
  5. #include <cmath>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <string>
  10. #include <queue>
  11. #include <list>
  12. #include <memory>
  13.  
  14. template <class T>
  15. class segment_tree
  16. {
  17. private:
  18.   const std::size_t size;
  19.   const std::unique_ptr<T[]> data;
  20.   std::function<T (const T&, const T&)> func;
  21.   const T neitral;
  22.  
  23.   void update(std::size_t ind)
  24.   {
  25.     data[ind] = func(data[2 * ind], data[2 * ind + 1]);
  26.     if (ind > 1)
  27.       update(ind / 2);
  28.   }
  29.   T query_inter(std::size_t l, std::size_t r, std::size_t L, std::size_t R, std::size_t ind) const
  30.   {
  31.     if (r <= L || R <= l)
  32.       return neitral;
  33.     else if (l <= L && r >= R)
  34.       return data[ind];
  35.     else
  36.     {
  37.       std::size_t M = (L + R) / 2;
  38.       return func(query_inter(l, r, L, M, 2 * ind), query_inter(l, r, M, R, 2 * ind + 1));
  39.     }
  40.   }
  41. public:
  42.   template <class iter>
  43.   segment_tree(const iter& start, const iter& end, const std::function<T (const T&, const T&)> &f, const T& zero)
  44.     : size(std::size_t(1) << std::size_t(ceil(log2(end - start)))), data(std::make_unique<T[]>(2 * size)), func(f), neitral(zero)
  45.   {
  46.     iter start_cpy = start;
  47.     for (std::size_t i = size; i < 2 * size; i++)
  48.     {
  49.       if (start_cpy == end)
  50.         for (; i < 2 * size; i++)
  51.           data[i] = zero;
  52.       else
  53.         data[i] = *start_cpy++;
  54.     }
  55.     for (std::size_t i = size / 2; i < size; i++)
  56.       update(i);
  57.   }
  58.   void set(std::size_t ind, const T& val)
  59.   {
  60.     data[ind + size] = val;
  61.     update((ind + size) / 2);
  62.   }
  63.   const T& get(std::size_t ind)
  64.   {
  65.     return data[ind + size];
  66.   }
  67.   T query(std::size_t l, std::size_t r) const
  68.   {
  69.     return query_inter(l, r, 0, size, 1);
  70.   }
  71.   ~segment_tree(void) = default;
  72. };
  73.  
  74. int main(void)
  75. {
  76.   std::ios::sync_with_stdio(false);
  77.   std::cin.tie(nullptr);
  78.   std::cout.tie(nullptr);
  79.  
  80.   unsigned n, m, t;
  81.   int x, y;
  82.   std::cin >> n;
  83.   std::unique_ptr<int[]> a = std::make_unique<int[]>(n);
  84.   for (unsigned i = 0; i < n; i++)
  85.     std::cin >> a[i];
  86.   segment_tree<int> ST(&a[0], &a[n], ([](const int& a, const int& b)->int{return a + b;}), 0);
  87.   a.release();
  88.   std::cin >> m;
  89.   while (m-- > 0)
  90.   {
  91.     std::cin >> t >> x >> y;
  92.     if (t == 1)
  93.       ST.set(x - 1, ST.get(x - 1) + y);
  94.     else
  95.       std::cout << ST.query(x - 1, y) << '\n';
  96.   }
  97.  
  98.   // system("pause");
  99.   return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement