Диапазон в сумме диапазона с обновлением точки
Нам дан массив A с N элементами, а также N диапазонами, каждый из которых имеет вид [L, R]. Позвоните значение диапазона сумма всех элементов в A от индекса L до индекса R включительно.
Пример: пусть Array A = [2 5 7 9 8] и заданный диапазон равен [2,4], тогда значение этого диапазона равно 5 + 7 + 9 = 21
Теперь нам дается Q запросов на каждый запрос одного из 2 типов:
1. 0 X Y : It means change Xth element of array to Y.
2. 1 A B : It means we need to report the sum of values of ranges from A to B.
Пример : Пусть массив A = [2 3 7 8 6 5] и пусть у нас есть 3 диапазона:
R1: [1,3] Then value corresponding to this range is 2+3+7=12
R2: [4,5] Then value corresponding to this range is 8+6=14
R3: [3,6] Then value corresponding to this range is 7+8+6+5=26
Теперь пусть у нас есть 3 запроса:
Q1: 1 1 2
Then here answer is value of Range1 + value of Range2 = 12+14=26
Q2: 0 2 5
It means Change 2nd element to 5 from 3.It will change the result of Range 1.
Now value of Range1 becomes 2+5+7=14
Q3: 1 1 2
Then here answer is value of Range1 + value of Range2 = 14+14=28
Как это сделать, если у нас есть 10 ^ 5 запросов и N также до 10 ^ 5. Как эффективно сообщать в Queries2?
Мой подход: Первый запрос может быть легко обработан. Я могу построить дерево сегментов из массива. Я могу использовать его для вычисления суммы интервалов в первом массиве (элемент во втором массиве). Но как я могу обработать второй запрос в O (log n)? В худшем случае элемент, который я обновляю, будет находиться во всех интервалах во втором массиве.
Мне нужно решение O (Qlog N) или O (Q (logN) ^ 2).
Очевидно, что мы не можем иметь O (N) для каждого запроса. Поэтому, пожалуйста, помогите получить эффективный способ
Мой текущий код:
#include<bits/stdc++.h>
using namespace std;
long long arr[100002],i,n,Li[100002],Ri[100002],q,j;
long long queries[100002][2],query_val[100002],F[100002],temp;
long long ans[100002];
int main()
{
scanf("%lld",&n);
for(i=1;i<=n;i++)
scanf("%lld",&arr[i]);
for(i=1;i<=n;i++)
{
scanf("%lld%lld",&Li[i],&Ri[i]);
}
for(i=1;i<=n;i++)
{
F[n] = 0;
ans[i] = 0;
}
scanf("%lld",&q);
for(i=1;i<=q;i++)
{
scanf("%lld",&query_val[i]);
scanf("%lld%lld",&queries[i][0],&queries[i][1]);
}
for(i=1;i<=n;i++)
{
for(j=Li[i];j<=Ri[i];j++)
{
F[i] = F[i] + arr[j];
}
}
long long diff;
long long ans_count = 0,k=1;
for(i=1;i<=q;i++)
{
if(query_val[i] == 1)
{
temp = arr[queries[i][0]];
arr[queries[i][0]] = queries[i][1];
diff = arr[queries[i][0]] - temp;
for(j=1;j<=n;j++)
{
if(queries[i][0]>=Li[j] && queries[i][0]<=Ri[j])
F[j] = F[j] + diff;
++k;
}
}
else if(query_val[i] == 2)
{
++ans_count;
for(j=queries[i][0];j<=queries[i][1];j++)
ans[ans_count] = ans[ans_count] + F[j];
}
}
for(i=1;i<=ans_count;i++)
{
printf("%lld\n",ans[i]);
}
return 0;
}
Хотя код правильный, но для больших тестовых случаев это занимает огромное время. Пожалуйста, помогите
Решение
Вы можете использовать дерево сегментов. http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/
#include <cstdio>
const int MAX_N = 1000003;
int tree[(1 << 21) + 3], a[MAX_N], N, M;
int x, y;
int query(int n, int l, int r) {
if(l > y || r < x) {
return 0;
}
if(l >= x && r <= y) {
return tree[n];
}
int q = query(2*n, l, (l + r)/2);
int p = query(2*n + 1, (l + r)/2 + 1, r);
return p + q;
}
void init(int n, int l, int r) {
if(l == r) {
tree[n] = a[l];
return;
}
init(2*n, l, (l + r)/2);
init(2*n + 1, (l + r)/2 + 1, r);
tree[n] = tree[2*n] + tree[2*n + 1];
}
void update(int n, int l, int r) {
if(l > y || r < x)
return;
if(l == r && x == r) {
tree[n] = y;
return;
}
else if(l == r) {
return;
}
update(2*n, l, (l + r)/2);
update(2*n + 1, (l + r)/2 + 1, r);
tree[n] = tree[2*n] + tree[2*n + 1];
}
int main() {
scanf("%d%d", &N, &M);
for(int i = 0; i < N; i++) {
scanf("%d", &a[i]);
}
init(1, 0, N - 1);
for(int i = 0; i < M; i++) {
int c;
scanf("%d%d%d", &c, &x, &y);
if(!c) {
a[x] = y;
update(1, 0, N - 1);
} else {
printf("%d\n", query(1, 0, N - 1));
}
}
return 0;
}
Основная идея заключается в расширении массива элементов в двоичное дерево. Каждый узел этого дерева содержит информацию о сумме элементов его дочерних элементов. И вы можете легко узнать, какой диапазон покрывает некоторый узел, применяя этот трюк:
Корень содержит информацию о дальности [1,N],
Левый ребенок корня держит информацию о диапазоне [1, int(N/2)],
Правый ребенок корня держит информацию о диапазоне [int(N/2)+1, N],
В общем, если узел «А» содержит информацию о диапазоне [l, r], Потом оставил ребенка
содержит информацию о диапазоне [l, int((l+r)/2)] и правильный ребенок держит информацию
о диапазоне [int((l+r)/2)+1, r],
Существует также хороший прием для представления двоичного дерева в массиве.
Допустим, вы держите свое дерево в массиве «дерево» (как я делаю, мой код). Тогда корень этого
дерево будет в tree[1], Левый ребенок корня будет tree[2] и правое дитя дерева
корень будет tree[3],
В общем, если вы находитесь на узле n тогда его левый ребенок 2*n и правильный ребенок 2*n + 1,
Вот почему я звоню своим query а также update функция с (1, 0, N — 1). Я начинаю с корневого узла 1, И диапазон, который я покрываю этим узлом i [0, N-1]. И я всегда пытаюсь найти первый узел, который вписывается в диапазон, для которого мне нужно вычислить сумму.
Это начало. Попробуйте погуглить больше о сегментных деревьях. Когда вы начнете исследовать, вы увидите, что есть несколько способов представить свое дерево.
Удачи. 🙂
Другие решения