Невозможно найти дерево сечений ошибок: минимум в подмассиве - PullRequest
Новая
       20

Невозможно найти дерево сечений ошибок: минимум в подмассиве

0 голосов
/ 05 апреля 2019

Я новичок в структурах данных и алгоритме и не могу найти ошибку в своем коде для вопроса

Минимальный диапазон запросов

Учитывая массив A размера N, существует два типа запросов к этому массиву.

  1. q l r: в этом запросе необходимо вывести минимум в подмассиве A [l: r].
  2. u x y: в этом запросе вам нужно обновить A [x] = y.

Входные данные: первая строка тестового примера содержит два целых числа, N и Q, размер массива A и количество запросов.

Вторая строка содержит N целых чисел, разделенных пробелом, элементы A. Следующие Q строк содержат один из двух запросов.

Выход:

Для каждого запроса типа 1 выведите минимальный элемент в подмассиве A [l: r].

Ограничения: 

1 ≤ N,Q,y ≤ 10^5
1 ≤ l,r,x≤N

#include<bits/stdc++.h>

using namespace std;

long a   [100001];
//global array to store input

long tree[400004];  
//global array to store tree

// FUNCTION TO BUILD SEGMENT TREE //////////

void build(long i,long start,long end)  //i = tree node  

{

    if(start==end)

    {
        tree[i]=a[start];

        return;

    }

    long mid=(start+end)/2;

    build(i*2,start,mid);

    build(i*2+1,mid+1,end);

    tree[i] = min(tree[i*2] , tree[i*2+1]);

}

//  FUNCTION TO UPDATE SEGMENT TREE //////////

void update  (long i,long start,long end,long idx,long val)

//idx = index to be updated 

// val = new value to be given at that index

{

    if(start==end)

        tree[i]=a[idx]=val;

    else
    {
        int mid=(start+end)/2;

        if(start <= idx and idx <= mid)

            update(i*2,start,mid,idx,val);

        else

            update(i*2+1,mid+1,end,idx,val);

        tree[i] = min(tree[i*2] , tree[i*2+1]);

    }

}

// FUNCTION FOR QUERY

long query(long i,long start,long end,long l,long r)   
{
    if(start>r || end<l || start > end)

        return INT_MAX;
    else

        if(start>=l && end<=r)

        return tree[i];

    long mid=(start+end)/2;

    long ans1 = query(i*2,start,mid,l,r);
    long ans2 = query(i*2+1,mid+1,end,l,r);

    return min(ans1,ans2);

}

int main()

{

    long n,q;

    cin>>n>>q;

    for(int i=0 ; i<n ; i++)

        cin>>a[i];

    //for(int i=1 ; i<2*n ; i++)    cout<<tree[i]<<"  ";   cout<<endl;

    build(1,0,n-1);

    //for(int i=1 ; i<2*n ; i++)    cout<<tree[i]<<"  ";    cout<<endl;


    while(q--)
    {
            long l,r;


            char ch;

            cin>>ch>>l>>r;

            if(ch=='q')

                cout<<query(1,0,n-1,l-1,r-1)<<endl;

            else

                update(1,0,n-1,l,r);

    }

    return 0;

}

Пример: ввод 

5 15
1 5 2 4 3
q 1 5
q 1 3
q 3 5
q 1 5
q 1 2
q 2 4
q 4 5
u 3 1
u 3 100
u 3 6
q 1 5
q 1 5
q 1 2
q 2 4
q 4 5

Ожидаемый результат: 

1
1
2
1
1
2
3
1
1
1
4
3

1 Ответ

0 голосов
/ 16 апреля 2019

Похоже, что все заданные значения предполагают индексирование на основе 1: 1 ≤ l,r,x ≤ N

Вы решили построить дерево сегментов с индексацией на основе 0, поэтому все запросы и обновления также должны использовать одинаковую индексацию.

Так что эта часть неверна, потому что вам нужно установить A [x] = y, и поскольку вы используете индексирование на основе 0, ваш код на самом деле устанавливает A [x + 1] = y 

update(1,0,n-1,l,r);

Исправитьизмените это на это: 

update(1,0,n-1,l-1,r);
...