Тема: Дерево Фенвика
Написано, что находит максимум/минимум только на отрезке [0;R]. У меня есть реализация, которая ищет на отрезке [L;R], могу скинуть или сам ее знаешь Короче статью стоит подправить
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Feedback » Дерево Фенвика
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Написано, что находит максимум/минимум только на отрезке [0;R]. У меня есть реализация, которая ищет на отрезке [L;R], могу скинуть или сам ее знаешь Короче статью стоит подправить
Напиши сюда.
Реализации за log N не знаю, хотя слышал когда-то про гипотетическое существование такой.
#include <iostream>
#include <cstdio>
#include <memory.h>
#define maxn 10000
#define inf 1000000000
using namespace std;
int m[maxn],n,l[maxn],r[maxn];
int prev(int x)
{
return (x&(x-1));
}
int next(int x)
{
return ((x<<1)-prev(x));
}
void modify(int pos, int value)
{
int p;
for (p=pos;p<=n;p=next(p)) r[p]=max(r[p],value);
m[pos]=max(m[pos],value);
for (p=pos;p>0;p=prev(p)) l[p]=max(l[p],value);
}
int findmax(int ll,int rr)
{
int res,p;
res=-inf;
for (p=ll;next(p)<=rr;p=next(p)) res=max(res,l[p]);
res=max(res,m[p]);
for (p=rr;prev(p)>=ll;p=prev(p)) res=max(res,r[p]);
return res;
}
void init(void)
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
cin>>n;
int x,i;
for (i=1;i<=n;i++)
m[i]=r[i]=l[i]=-inf;
for (i=1;i<=n;i++)
{
cin>>x;
modify(i,x);
}
}
void sol(void)
{
int i,j;
for (i=1;i<=n;i++,cout<<endl)
for (j=i;j<=n;j++)
cout<<findmax(i,j)<<" ";
}
int main(void)
{
init();
sol();
cin>>n;
return 0;
}
Тут сама реализация и за одно вводит массив на N элементов и выводит максимумы для всех возможных L и R. Самый большой минус - элементы можно только увеличивать, но это компенсируется большей скоростью работы, чем RMQ, и простотой написания. Дерево Фенвика для нахождения максимумов на интервале называется "максимизатор", для минимумов - "минимизатор"(в частности для максимумов на интервале [0;R] - "максиматор", для сумм - "сумматор"). А вообще на двумерную матрицу эта штука довольно трудно пишется.
Я почему-то сомневаюсь, что искать максимум на отрезке таким образом будет быстрее, чем не рекурсивным деревом отрезков. Да и пишется оно точно не длиннее.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Feedback » Дерево Фенвика