하늘에서 별이 [L,R]에 떨어지고 왼쪽부터 순서대로 1, 2 ··· R - L + 1개가 떨어집니다.
점 X에 몇개의 별이 떨어졌는지 출력하는 문제입니다.
구간 덧셈, 포인트 쿼리이므로 펜윅 트리로 풀 수 있습니다.
문제는 업데이트를 할 때 같은 값을 업데이트 하는게 아니라 각각 다른 숫자들을 업데이트를 해야 합니다.
하나하나 업데이트를 할 수 없으므로 다른 방법을 찾아야 하는데
[L,R]의 범위를 업데이트 하면 되면 L부터 R까지 1,2 … R-N+1의 숫자를 업데이트하게 됩니다.
그렇다면 구간 업데이트를 할 때 L을 따로 저장하게 되면
[L,R]의 인덱스 X에 대한 업데이트 값은 X - L + 1로 업데이트 할 값을 알 수 있습니다.
[1, 5]에 별이 떨어지면 구간에 1이 저장됩니다.
[3,5]에 별이 더 떨어진다 하면 구간에 3을 저장해야 하는데 3~5에는 이미 값이 있으므로 더해줍니다.
여기서 3에 떨어진 별의 개수를 구하겠습니다.
[1,5]에서 1, [3,5]에서 3을 더해줍니다.
개수를 구하려면 (3 - 1 + 1) + (3 - 3 + 1)로 구할 수 있는데
합으로 구했었으므로 (인덱스 업데이트 횟수 * 인덱스 - 펜윅 트리에 저장한 (L-1)의 합)으로 값을 구할 수 있습니다.
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
#define RFOR(a,b,c) for(int a = (b); a >= (c); a--)
#define all(x) (x).begin(), (x).end()
#define ll long long
#define fs first
#define sd second
#define vi vector <int>
#define vvi vector <vi>
#define pii pair<int,int>
#define ppi pair <pii,pii>
using namespace std;
struct FT {
vector <pair<ll, ll>> tree; // first-업데이트 횟수, second-인덱스 합
int size;
FT(int n) :size(n) {
tree.resize(n + 1);
}
void update(int a, int b) { update(a, 1, a), update(b + 1, -1, a); }
void update(int idx, int val, int a) {
while (idx <= size) {
tree[idx].fs += val;
tree[idx].sd += (a - 1) * val;
idx += (idx & -idx);
}
}
ll query(int idx) {
ll ans = 0;
int i = idx;
while (i) {
ans += 1LL * idx * tree[i].fs - tree[i].sd;
i -= (i & -i);
}
return ans;
}
~FT() {
tree.clear();
}
};
int main() {
FIO;
int n; cin >> n;
FT ft(n);
vi v(n + 1);
FOR(i, 1, n) cin >> v[i];
int m; cin >> m;
while (m--) {
int t, a, b;
cin >> t >> a;
if (t == 1) {
cin >> b;
ft.update(a, b);
}
else cout << 1LL * v[a] + ft.query(a) << '\n';
}
return 0;
}