Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /******************************************************************************
- Online C++ Compiler.
- Code, Compile, Run and Debug C++ program online.
- Write your code in this editor and press "Run" button to compile and execute it.
- *******************************************************************************/
- #include <iostream>
- #include <vector>
- using namespace std;
- vector<int> tree;
- int getSum(int q, int tl, int tr, int l, int r) {
- if(tl >= l && tr <= r)
- return tree[q];
- if(tl >= r || tr <= l)
- return 0;
- int mid = (tl + tr)/2;
- int getl = getSum(q*2, tl, mid, l, r);
- int getr = getSum(q*2+1, mid, tr, l, r);
- return getl + getr;
- }
- int main()
- {
- //15:03 - 15:13
- int n;
- cin >> n;
- tree.resize(4*n, 0);
- int k = 1;
- while(k < n)
- k*=2;
- for(int i = 0; i < n; i++) {
- int uk1 = k+i;
- cin >> tree[uk1];
- while(uk1 != 1) {
- tree[uk1/2] = tree[(uk1/2)*2] + tree[(uk1/2)*2+1];
- uk1/=2;
- }
- }
- int kkk;
- cin >> kkk;
- for(int i = 0; i < kkk; i++) {
- char ch;
- int a, b;
- cin >> ch;
- if(ch == '+') {
- cin >> a >> b;
- int uk1 = k+a;
- tree[uk1] = b;
- while(uk1 != 1) {
- tree[uk1/2] = tree[(uk1/2)*2] + tree[(uk1/2)*2+1];
- uk1/=2;
- }
- }
- if(ch == '?') {
- cin >> a >> b;
- cout << "[" << a << ", " << b << "): " << getSum(1, 0, k, a, b) << '\n';
- }
- for(int j = 0; j < k; j++)
- cout << tree[k+j] << ' ';
- cout << '\n';
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment