Запутался в этапах обработки запросов в дереве Фенвика - PullRequest
Новая
       16

Запутался в этапах обработки запросов в дереве Фенвика

0 голосов
/ 06 июля 2019

Я недавно начал изучать дерево Фенвика для ответа на проблему с диапазонными запросами. Но я запутался в 2 типах обработки запросов:

  1. Сначала я предварительно обработал свой ввод и построил для него дерево Фенвика, а затем вычислял ответ для каждого запроса один за другим.

  2. Построение и ответ на запросы выполняются одновременно. Я отвечаю на вопросы и строю свое дерево Фенвика.

И я обнаружил проблему, которая спрашивает: количество различных элементов в [L, R] для данного массива. Дан массив запросов вида [L, R]. Теперь в этой задаче я сначала строю дерево, а затем отвечаю на запросы один за другим. Я получил неправильный ответ на многие вопросы. Но когда я сортирую запросы по их R-значению и обрабатываю запрос одновременно со строительным деревом, я получаю правильный ответ.

Ниже приведен код, в котором дерево построения и ответ на запрос выполняются одновременно: 

#include<bits/stdc++.h> 
using namespace std; 

const int MAX = 1000001; 
struct Query 
{ 
    int l, r, idx; 
}; 

bool cmp(Query x, Query y) 
{ 
    return x.r < y.r; 
} 

void update(int idx, int val, int bit[], int n) 
{ 
    for (; idx <= n; idx += idx&-idx) 
        bit[idx] += val;  
}

int query(int idx, int bit[], int n) 
{ 
    int sum = 0; 
    for (; idx>0; idx-=idx&-idx) 
        sum += bit[idx]; 
    return sum; 
} 

 void answeringQueries(int arr[], int n, Query queries[], int q) 
 { 
    // initialising bit array 
    int bit[n+1]; 
    memset(bit, 0, sizeof(bit)); 

    // holds the rightmost index of any number 
    // as numbers of a[i] are less than or equal to 10^6 
    int last_visit[MAX]; 
    memset(last_visit, -1, sizeof(last_visit)); 

    // answer for each query 
    int ans[q]; 
    int j = 0; 

     for (int i = 0; i < q; i++)  
     { 
        while (j <= queries[i].r)  
        { 

            if (last_visit[arr[j]] != -1) 
                update(last_visit[arr[j]]+1,-1,bit,n); 


            update(j+1,1,bit,n); 
            last_visit[arr[j]] = j; 
            j++; 
        } 
        ans[queries[i].idx] = 
                     query(queries[i].r + 1, bit, n)- 
                     query(queries[i].l, bit, n);
     }
    // print answer for each query 
    for (int i=0; i<q; i++) 
        cout << ans[i] << endl; 
} 

int main() { 
    int a[] = {1, 1, 1, 1, 1}; 
    int n = sizeof(a)/sizeof(a[0]); 
    Query queries[3]; 
    queries[0].l = 0; 
    queries[0].r = 0; 
    queries[0].idx = 0; 
    queries[1].l = 1; 
    queries[1].r = 3; 
    queries[1].idx = 1; 
    queries[2].l = 2; 
    queries[2].r = 4; 
    queries[2].idx = 2; 
    int q = sizeof(queries)/sizeof(queries[0]); 
    sort(queries, queries+q, cmp); 
    answeringQueries(a, n, queries, q); 
    return 0; 
}

Мой вопрос таков: как мне узнать, должен ли я отвечать на запросы одновременно с построением дерева или должен отвечать на них один за другим после построения дерева.

...