competitive_programming/FenwickTreeRangeQuery.cpp at master · Karthik-Ragunath/competitive_programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
#define ll long long int

void createFenwickTree(vector< ll > &fenwickTree, ll index, ll endingIndex, ll value)
{
    for(; index <= endingIndex;)
    {
        fenwickTree[index] += value;
        index += (index & -index);
    }
}

void updateFenwickTree(vector< ll > &fenwickTree, ll index, ll endingIndex, ll value)
{
    for(; index <= endingIndex;)
    {
        fenwickTree[index] += value;
        index += (index & -index);
    }
}

ll rangeQuery(vector< ll > &fenwickTree, ll endIndex)
{
    ll sum = 0;
    for(ll index = endIndex; index > 0;)
    {
        sum += fenwickTree[index];
        index -= (index & -index);
    }
    return sum;
}

int main()
{
    ll n, q;
    cin >> n >> q;
    vector< ll > values(n + 1);
    vector< ll > fenwickTree(n + 1);
    for(ll i = 1; i <= n; i++)
    {
        cin >> values[i];
        createFenwickTree(fenwickTree, i, n, values[i]);
    }
    for(ll i = 0; i < q; i++)
    {
        ll type;
        cin >> type;
        if(type == 1)
        {
            ll index, value;
            cin >> index >> value;
            ll difference = value - values[index];
            values[index] = value;
            updateFenwickTree(fenwickTree, index, n, difference);
        }
        else
        {
            ll startRange, endRange;
            cin >> startRange >> endRange;
            ll solution = rangeQuery(fenwickTree, endRange) - rangeQuery(fenwickTree, startRange - 1);
            cout << solution << endl;
        }
    }
    return 0;
}