Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <algorithm>
- #include <functional>
- #include <cmath>
- #include <vector>
- #include <set>
- #include <map>
- #include <string>
- #include <queue>
- #include <list>
- #include <memory>
- template <class T>
- class segment_tree
- {
- private:
- const std::size_t size;
- const std::unique_ptr<T[]> data;
- std::function<T (const T&, const T&)> func;
- const T neitral;
- void update(std::size_t ind)
- {
- data[ind] = func(data[2 * ind], data[2 * ind + 1]);
- if (ind > 1)
- update(ind / 2);
- }
- T query_inter(std::size_t l, std::size_t r, std::size_t L, std::size_t R, std::size_t ind) const
- {
- if (r <= L || R <= l)
- return neitral;
- else if (l <= L && r >= R)
- return data[ind];
- else
- {
- std::size_t M = (L + R) / 2;
- return func(query_inter(l, r, L, M, 2 * ind), query_inter(l, r, M, R, 2 * ind + 1));
- }
- }
- public:
- template <class iter>
- segment_tree(const iter& start, const iter& end, const std::function<T (const T&, const T&)> &f, const T& zero)
- : size(std::size_t(1) << std::size_t(ceil(log2(end - start)))), data(std::make_unique<T[]>(2 * size)), func(f), neitral(zero)
- {
- iter start_cpy = start;
- for (std::size_t i = size; i < 2 * size; i++)
- {
- if (start_cpy == end)
- for (; i < 2 * size; i++)
- data[i] = zero;
- else
- data[i] = *start_cpy++;
- }
- for (std::size_t i = size / 2; i < size; i++)
- update(i);
- }
- void set(std::size_t ind, const T& val)
- {
- data[ind + size] = val;
- update((ind + size) / 2);
- }
- const T& get(std::size_t ind)
- {
- return data[ind + size];
- }
- T query(std::size_t l, std::size_t r) const
- {
- return query_inter(l, r, 0, size, 1);
- }
- ~segment_tree(void) = default;
- };
- int main(void)
- {
- std::ios::sync_with_stdio(false);
- std::cin.tie(nullptr);
- std::cout.tie(nullptr);
- unsigned n, m, t;
- int x, y;
- std::cin >> n;
- std::unique_ptr<int[]> a = std::make_unique<int[]>(n);
- for (unsigned i = 0; i < n; i++)
- std::cin >> a[i];
- segment_tree<int> ST(&a[0], &a[n], ([](const int& a, const int& b)->int{return a + b;}), 0);
- a.release();
- std::cin >> m;
- while (m-- > 0)
- {
- std::cin >> t >> x >> y;
- if (t == 1)
- ST.set(x - 1, ST.get(x - 1) + y);
- else
- std::cout << ST.query(x - 1, y) << '\n';
- }
- // system("pause");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement