1

Тема: Дерево Фенвика

Написано, что находит максимум/минимум только на отрезке  [0;R]. У меня есть реализация, которая ищет на отрезке [L;R], могу скинуть или сам ее знаешь smile Короче статью стоит подправить

2

Re: Дерево Фенвика

Напиши сюда.

Реализации за log N не знаю, хотя слышал когда-то про гипотетическое существование такой.

3

Re: Дерево Фенвика

#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] - "максиматор", для сумм - "сумматор"). А вообще на двумерную матрицу эта штука довольно трудно пишется.

4

Re: Дерево Фенвика

Я почему-то сомневаюсь, что искать максимум на отрезке таким образом будет быстрее, чем не рекурсивным деревом отрезков. Да и пишется оно точно не длиннее.