Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //B
- #include <vector>
- #include <iostream>
- #include <cassert>
- #include <climits>
- // 13 = 8 + 4 + 1 0:00001101 1:00000110 2:00000011 3:00000001 4:00000000
- int next_2_degree(int value)
- {
- int i = 0;
- while(value >> i) ++i;
- return 1 << i;
- }
- //-----------------------------------------------------------------------------
- class SegmentTree {
- public:
- SegmentTree(const std::vector<int>& arr, int defaultValue);
- int Sum(int left, int right) const;
- void Update(int val, int pos);
- private:
- std::vector <int> sum_;
- int default_;
- void build(int index, int left, int right);
- void update(int index, int left, int right, int val, int pos);
- int sum(int index, int i_left, int i_right, int left, int right) const;
- };
- SegmentTree::SegmentTree (const std::vector<int>& arr, int defaultValue)
- : sum_(next_2_degree(arr.size()) * 2, defaultValue),
- default_(defaultValue) {
- std::copy(arr.begin(), arr.end(), sum_.begin() + sum_.size() / 2 - 1);
- build(0, 0, sum_.size() / 2 - 1);
- }
- void SegmentTree::build(int index, int left, int right) {
- if (left == right) return;
- const int mid = (left + right) >> 1;
- build(2 * index + 1, left, mid);
- build(2 * index + 2, mid + 1, right);
- sum_[index] = sum_[2 * index + 1] + sum_[2 * index + 2];
- }
- void SegmentTree::Update(int val, int pos) {
- if (pos % 2 == 0) {
- update(0, 0, sum_.size() / 2 - 1, val, pos);
- } else {
- update(0, 0, sum_.size() / 2 - 1, (-1 * val), pos);
- }
- return;
- }
- void SegmentTree::update(int index, int left, int right, int val, int pos) {
- if (left == right) {
- sum_[index] = val;
- return;
- }
- const int mid = (left + right) >> 1;
- if (pos <= mid) {
- update(2 * index + 1, left, mid, val, pos);
- }
- if (pos > mid) {
- update(2 * index + 2, mid + 1, right, val, pos);
- }
- sum_[index] = sum_[2 * index + 1] + sum_[2 * index + 2];
- }
- int SegmentTree::Sum(int left, int right) const {
- if (left % 2 == 0) {
- return sum(0, 0, sum_.size() / 2 - 1, left, right);
- } else {
- return sum(0, 0, sum_.size() / 2 - 1, left, right) * (-1);
- }
- }
- int SegmentTree::sum(int index, int i_left, int i_right, int left, int right) const {
- //std::cout << "! " << i_left << " " << i_right << " " << left << " " << right << "\n";
- assert(i_left <= i_right && left <= right);
- if (right < i_left) { return default_; }
- if (left > i_right) { return default_; }
- if (left <= i_left && i_right <= right) {
- return sum_[index];
- }
- const int mid = (i_left + i_right) / 2;
- return sum(2 * index + 1, i_left, mid, left, right) +
- sum(2 * index + 2, mid + 1, i_right, left, right);
- }
- //-----------------------------------------------------------------------------
- int main() {
- int n;
- std::cin >> n;
- std::vector <int> a(n);
- for (int i = 0; i < n; ++i) {
- std::cin >> a[i];
- if (i % 2 == 1) {
- a[i] *= (-1);
- }
- }
- SegmentTree tree(a, 0);
- int m;
- std::cin >> m;
- while (m--) {
- int k;
- int x, y;
- std::cin >> k >> x >> y;
- if (k == 1) {
- --x;
- --y;
- std::cout << tree.Sum(x, y) << "\n";
- } else {
- --x;
- tree.Update(y, x);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement