Прибавление на отрезке и точечный запрос за O(log n)
n, m = map(int, input().split())
F = [[0] * 2 for _ in range(n + 1)]
def get1(r, f):
z = 0
while r > 0:
z += F[r][f]
r -= r & -r
return z
def get(r):
return get1(r, 0) * r - get1(r, 1)
def add1(i, x, f):
while i <= n:
F[i][f] += x
i += i & -i
def add(l, r, x):
add1(l, x, 0)
add1(r + 1, -x, 0)
add1(l, x * (l - 1), 1)
add1(r + 1, -x * r, 1)
for _ in range(m):
s = list(input().split())
if s[0] == "+":
l, r, x = int(s[1]), int(s[2]), int(s[3])
add(l, r, x)
else:
print(get(int(s[1])) - get(int(s[1]) - 1))
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
vector<vector<ll>> F;
ll get1(int r, int f) {
ll z = 0;
while (r > 0) {
z += F[r][f];
r -= r & -r;
}
return z;
}
ll get(int r) {
return get1(r, 0) * r - get1(r, 1);
}
void add1(int i, ll x, int f) {
while (i <= n) {
F[i][f] += x;
i += i & -i;
}
}
void add(int l, int r, ll x) {
add1(l, x, 0);
add1(r + 1, -x, 0);
add1(l, x * (l - 1), 1);
add1(r + 1, -x * r, 1);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int m;
cin >> n >> m;
F.assign(n + 1, vector<ll>(2, 0));
for (int i = 0; i < m; i++) {
char type;
cin >> type;
if (type == '+') {
int l, r, x;
cin >> l >> r >> x;
add(l, r, x);
} else {
int p;
cin >> p;
cout << get(p) - get(p - 1) << "\n";
}
}
return 0;
}
Модифицированное дерево Фенвика позволяет выполнять прибавление на отрезке [l, r] и точечный запрос значения элемента за O(log n). Для этого используется техника двух массивов — диапазонных и точечных запросов.
Вместо хранения самих значений, мы храним два дерева Фенвика, которые позволяют восстановить значение элемента через сумму вкладов от всех обновлений.
Значение элемента p = get(p) - get(p-1), где get(r) — сумма префикса.
Сложность операций: O(log n) — каждая операция выполняется за время, пропорциональное количеству битов.
Пространственная сложность: O(n) — два дерева размера n+1.
Ввод:
n m — количество элементов и количество запросов+ l r x — прибавить x ко всем элементам на отрезке [l, r]? p — вывести значение элемента pВывод:
10 6
+ 1 5 3
? 3
+ 3 7 2
? 3
? 5
+ 1 10 1
? 5
Вывод:
3
5
5
2
Пояснение:
Изначально все нули.
После + 1 5 3: A[3] = 3 → вывод 3
После + 3 7 2: A[3] = 3+2=5, A[5] = 3+2=5 → вывод 5, 5
После + 1 10 1: A[5] = 5+1=6 → вывод 6
Введите запросы: