Range update/ Query Binary Index Tree

Question

Range update/ Query Binary Index Tree

727 views Asked by Nakshatra At 25 November 2024 at 12:07

Problem Statement:

https://www.hackerrank.com/contests/epiccode/challenges/square-array

Given an array of integers A1,A2,…AN, you have to perform two types of queries in the array.

1 x y. Add 1×2 to Ax, add 2×3 to Ax+1, add 3×4 to Ax+2, add 4×5 to Ax+3, and so on until Ay.

2 x y. Find the sum of all integers from index x to index y modulo 109+7, i.e. find (Ax+Ax+1+⋯+Ay)mod(109+7).

You can assume that initially all the values in the array are 0.

Input Format:

The first line contains two space-separated integers, N and Q. N denotes the size of the array and Q denotes the number of queries.

Each of the next Q lines will contain a query of the form 1 x y or 2 x y.

Constraints:

1≤x≤y≤N 1≤N≤2×10^5 1≤Q≤2×10^5

Output Format For each query of the form 2 x y print the required answer.

Sample Input

10 5
1 1 10
2 2 7
1 4 8
1 5 6
2 6 6

Output:
166 
60

Explanation:

After the first query, the array is [2,6,12,20,30,42,56,72,90,110]. 
The answer for the second query is 6+12+20+30+42=166. 
After the third query, the array is [2,6,12,22,36,54,76,102,90,110]. 
After the fourth query, the array is [2,6,12,22,38,60,76,102,90,110]. 
The answer for the fifth query is 60.

One of the submitted solution:

#include <bits/stdc++.h>
const int N = 2 * 100005;
const long long MOD = 1000000007;
const long long INV = 333333336;

using namespace std;

int n;
int nQuery;

struct BIT {
    int bit[N];
    BIT() {
        memset(bit, 0, sizeof(bit));
    }

    void inc(int i, int v) {
        for (; i < N; i += i & -i) {
            bit[i] += v;
            bit[i] %= MOD;
        }
    }

    void incRange(int i, int j, int v) {
        inc(i, v); inc(j + 1, MOD - v);
    }

    int get(int i) {
        int res = 0;
        for (; i > 0; i -= i & -i)
            res = (res + bit[i]) % MOD;
        return res;
    }
} First, Second, Third, Const;

int sum(long long x, long long y) {
    return ((x + y) % MOD + MOD) % MOD;
}

void update(long long l, long long r) {
    Third.incRange(l, r, 1);
    Second.incRange(l, r, MOD - sum(l - 1, sum(l - 2, l - 3)));
    First.incRange(l, r, sum((l - 1) * (l - 2) % MOD, sum((l - 2) * (l - 3) % MOD, (l - 1) * (l - 3) % MOD)));
    Const.incRange(l, r, sum(MOD - (l - 1) * (l - 2) % MOD * (l - 3) % MOD, MOD));
    Const.incRange(r + 1, n, (r - l + 1) * (r - l + 2) % MOD * (r - l + 3) % MOD);
}

int getSum(long long x) {
    return (x * x % MOD * x % MOD * Third.get(x) % MOD + x * x % MOD * Second.get(x) % MOD + x * First.get(x) % MOD + Const.get(x)) % MOD * INV % MOD;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
#ifdef _LAD_
    freopen("square-array.txt", "r", stdin);
#endif // _LAD_
    cin >> n >> nQuery;
    int x, y, type;
    while (nQuery--) {
        cin >> type >> x >> y;
        if (type == 1) {
            update(x, y);
#ifdef _LAD_
            for (int i = 1; i <= n; ++i)
                cout << ((getSum(i) - getSum(i - 1) + MOD) % MOD) << ' ';
            cout << endl;
#endif // _LAD_
        }
        else
            cout << (getSum(y) - getSum(x - 1) + MOD) % MOD << '\n';
    }
    return 0;
}

Original Q&A