Please read the new rule regarding the restriction on the use of AI tools. ×

Aris12345's blog

Range Update Queries
By Aris12345, history, 4 years ago, In English

Hello, I am trying to solve this problem: https://cses.fi/problemset/task/1651. I don't know where my code is wrong, can you help me.

here is my code:

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;

int n, q, arr[MAXN], bit[MAXN];

void update(int x, int y) {
    for (; x <= n; x += x&-x) bit[x] += y;
}

int query(int x) {
    int ans = 0;
    for (; x > 0; x -= x&-x) ans += bit[x];
    return ans;
}

void range(int x, int y, int z) {
    update(x, z);
    update(y+1, -z);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        update(i, arr[i]);
    }
    while (q--) {
        int x, y, z, w;
        cin >> x;
        if (x == 1) { cin >> y >> z >> w; range(y, z, w); }
        else { cin >> y; cout << query(y)-query(y-1) << "\n"; }
    }
    return 0;
}

Thanks for your time!!!

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Range updates

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

For range updates and point queries while using BIT, the idea is to maintain such an array, that prefix sum of that array gives you the current array. So, incrementing a range $$$[l,r]$$$ by value $$$x$$$, means adding $$$x$$$ at $$$a[l]$$$ and subtracting $$$x$$$ at $$$a[r+1]$$$, so that when you take the prefix sum of these things, only the interval $$$[l,r]$$$ has $$$x$$$ added to it.

The problem is, you're doing this part fine, but you have done 2 other errors in this approach. update(i,arr[i]) would be incorrect here, because you don't maintain the actual array, and instead you need prefix sum to give you correct array. so you should replace that by range(i,i,arr[i]). The other error is, in this approach, your value at index $$$i$$$ will be $$$query(i)$$$ and not $$$query(i) - query(i-1)$$$, because again, we are maintaining such an array that prefix sum of it will give current element.

I remember you had asked another similar question regarding BIT, and I'd like to give you an advice, don't mug up the $$$query()$$$ and $$$update()$$$ functions as "Ok, query will give me the sum and update will update at the index", you need to understand what they are doing. You should have a look at this very good tutorial on BIT. This is another very good material on BIT, and many other DS and algos.

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What can we do if update(l,r,x) query is as follows: set v[i] = min(v[i],x) for l<=i<=r. And point query is to get v[i].

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      I don't know a way to do that with BIT / Fenwick tree, can't think of one right now. But it's standard with usual segment tree.

      If you are aware how segment trees work, then you might find this quick explanation helpful, otherwise you might want to learn about them.

      Explanation: For an update query on range, you keep going down to nodes which are completely inside the range, and then update that node with min operation. For a get query, just take min of everything on the way to that node in the segment tree.

      → Reply