Stupid question on Fenwick Tree

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
28:08:08
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя Indiot

Stupid question on Fenwick Tree

Автор Indiot, история, 10 месяцев назад, По-английски

Hi~

To be able to get the hell out of this grey color, i'm learning new data structures. One of those is Fenwick Tree. By copying code of others on the internet, i'm now able to perform some basic operations such as min / max/ sum on a specific interval. Now here come a new problem, how to find the maximum X * f(X) on range [0, r], f(X) here denotes the occurrences of X within that interval. Thank you all, I much appreciate it!

-8

Indiot
10 месяцев назад
16

Комментарии (16)

Написать комментарий?

VMaksimoski008

10 месяцев назад, # |

If I understood the problem correctly, you can solve the problem offline.

Since all queries have the same startpoint 0, sort them by their endpoint in ascending order.

Now you can you can compress all values in the array you are performing the queries and build a fenwick tree with size N where N is the number of distinct compressed values.

To process the queries maintain a pointer that only moves to the right. In the first query you move it from 0 to r1, in the second query from r1 to r2 and so on.

When you move the pointer to new index, you consider the value at that index, let it be X, then you add X on its position in the fenwick tree. To answer the query you just need to query the maximum value in the tree

→ Ответить

Indiot

10 месяцев назад, # ^ |

Hey, thanks for your detailed response! Actually the original problem requires update operation (add / remove element). So here is my code:

code

    ft get_max(int r) {
        ft ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret = max(ret, bit[r]);
        return ret;
    }

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1)){
            bit[idx] += delta;
        }
    }

But it does not give the right answer, where am I missing here? tks again

→ Ответить

VMaksimoski008

10 месяцев назад, # ^ |

You didn't specify that the problem has updates, so I thought you only have to answer queires. Sorry.

→ Ответить

Indiot

10 месяцев назад, # ^ |

full code


#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define fi first
#define se second

typedef long long ll;

const int N = 1e5 + 5;

int block_size;
int arr[N];
int id[N];

ll res = 0;

template<typename ft>
struct FenwickTree {
    vector<ft> bit;  // binary indexed tree
    int n;

    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    FenwickTree(vector<int> const &a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }
    ft get_max(int r) {
        ft ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret = max(ret, bit[r]);
        return ret;
    }

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1)){
            bit[idx] += delta;
        }
    }
};

FenwickTree<ll> fw(N);

void add(int idx){
	int x = arr[idx];
	fw.add(x, id[x]);
	res = fw.get_max(N - 1);
}
void remove(int idx){
	int x = arr[idx];
	fw.add(x, -id[x]);
	res = fw.get_max(N - 1);
}
struct Query {
    int l, r, idx;
    bool operator<(Query other) const {
        return make_pair(l / block_size, r) < make_pair(other.l / block_size, other.r);
    }
};
vector<ll> mo_s_algorithm(vector<Query> queries) {
    vector<ll> answers(queries.size());
    sort(queries.begin(), queries.end());

    // TODO: initialize data structure

    int cur_l = 0;
    int cur_r = -1;
    // invariant: data structure will always reflect the range [cur_l, cur_r]
    for(Query q : queries){
        while (cur_l > q.l) add(--cur_l);
        while (cur_r < q.r) add(++cur_r); 
        while (cur_l < q.l) remove(cur_l++); 
        while (cur_r > q.r) remove(cur_r--); 
        answers[q.idx] = res;
    }
    return answers;
}
void Solve(){
	int n, q;
	cin>>n>>q;
	vector<int> tmp(n);
	map<int, int> myMap;
	int cur = 1;
	for(int i = 0; i < n; i++){
		cin>>tmp[i];
		if(!myMap.count(tmp[i])){
			myMap[tmp[i]] = cur++;
		}
	}
	for(int i = 0; i < n; i++){
		arr[i] = myMap[tmp[i]];
		id[arr[i]] = tmp[i];
	}
	block_size = sqrt(n) + 1;

	vector<Query> v(q);
	for(int i = 0; i < q; i++){
		cin>>v[i].l>>v[i].r;
		v[i].l--; v[i].r--;
		v[i].idx = i;
	}
	vector<ll> res = mo_s_algorithm(v);
	for(auto x: res){
		cout<<x<<nl;
	}

}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	Solve();
}

Original problem (japanese)

→ Ответить

Indiot

10 месяцев назад, # ^ |

← Rev. 2 →

that's my fault to be honest

edit: never mind, i solved the problem

→ Ответить

VMaksimoski008

10 месяцев назад, # ^ |

How did you solved the problem?

→ Ответить

Indiot

10 месяцев назад, # ^ |

AC code

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define fi first
#define se second

typedef long long ll;

const int N = 1e5 + 5;

int block_size;

int cnt[N], id[N], arr[N];
ll t[2 * N];

void modify(int p, ll value) {  // set value at position p
  for (t[p += N] = value; p > 1; p >>= 1) t[p>>1] = max(t[p], t[p^1]);
}

ll query(int l, int r) {  // sum on interval [l, r)
  ll res = 0;
  for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
    if (l&1) res = max(res, t[l++]);
    if (r&1) res = max(res, t[--r]);
  }
  return res;
}
void add(int idx){
    int x = arr[idx];
    cnt[x]++;
    modify(x, (ll)cnt[x] * id[x]);
}
void remove(int idx){
    int x = arr[idx];
    cnt[x]--;
    modify(x, (ll)cnt[x] * id[x]);
}
struct Query {
    int l, r, idx;
    bool operator<(Query other) const {
        return make_pair(l / block_size, r) < make_pair(other.l / block_size, other.r);
    }
};
vector<ll> mo_s_algorithm(vector<Query> queries) {
    vector<ll> answers(queries.size());
    sort(queries.begin(), queries.end());

    // TODO: initialize data structure

    int cur_l = 0;
    int cur_r = -1;
    // invariant: data structure will always reflect the range [cur_l, cur_r]
    for(Query q : queries){
        while (cur_l > q.l) add(--cur_l);
        while (cur_r < q.r) add(++cur_r); 
        while (cur_l < q.l) remove(cur_l++);
        while (cur_r > q.r) remove(cur_r--); 
        answers[q.idx] = query(0, N - 1);
    }
    return answers;
}
void Solve(){
	memset(cnt, 0, sizeof(cnt));
	memset(t, 0, sizeof(t));
	int n, q;
	cin>>n>>q;
	vector<int> tmp(n);
	map<int, int> myMap;
	int cur = 1;
	for(int i = 0; i < n; i++){
		cin>>tmp[i];
		if(!myMap.count(tmp[i])){
			myMap[tmp[i]] = cur++;
		}
	}
	for(int i = 0; i < n; i++){
		arr[i] = myMap[tmp[i]];
		id[arr[i]] = tmp[i];
	}
	block_size = sqrt(n) + 1;

	vector<Query> v(q);
	for(int i = 0; i < q; i++){
		cin>>v[i].l>>v[i].r;
		v[i].l--; v[i].r--;
		v[i].idx = i;
	}
	vector<ll> res = mo_s_algorithm(v);
	for(auto x: res){
		cout<<x<<nl;
	}

}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	Solve();
}

Normal segment tree would not pass the time limit so I used efficient segment tree

→ Ответить

Papercut

10 месяцев назад, # |

← Rev. 2 →

Fun fact: Fenwick tree does not support non-invertible operations, that is, it's impossible to calculate $$$v[l] \circ v[l + 1] \circ \ldots \circ v[r]$$$ for an arbitrary $$$l, r$$$ if $$$\circ$$$ is $$$max/min/gcd$$$ etc. (however, we can support something like: 1) calculate minimum value among $$$v[l..r]$$$ 2) decrease $$$v[i]$$$ by $$$x$$$)

So, in general, your problem is not solvable with single Fenwick tree (but the comment above describes a decent solution).
P.S. I understand, that it is not part of your quiestion, but.. learning advanced (and not so advanced) data structures, you only become able to overkill some problems, while not improving your problem solving skills. The better option is to take a break (because when you're lost in desperation, your motivation level is really low) and get back to grinding as soon as you feel missed.
P.P.S. And yes, the previous paragraph is not like "stop learning useless algorithms, learn how to use binary search" — that's a problem i've been suffering from for a long time (like $$$80$$$% of time since i've started doing CP)

→ Ответить

Indiot

10 месяцев назад, # ^ |

that's an honest advice that every newbie needs, thank you!

→ Ответить

vstiff

10 месяцев назад, # ^ |

← Rev. 2 →

If you need non-reversible operations just use segment tree which is probably even simpler to implement and understand with comparable performance.

→ Ответить

estoy-re-sebado

10 месяцев назад, # |

← Rev. 3 →

+16

You don't need Fenwick tree here, just map. Given a fixed array we precompute all queries. Just walk the array from left to right maintaining a map<int,int> f; that counts occurrences of each value. Also, keep the maximum x*f[x] seen so far. That value is the answer to the current prefix, so we can store that in an array.

int n; cin >> n;
vector<int> a(n); forn(i,n) cin >> a[i];

map<int, int> f;
vector<long long> b(n);
long long ans = 0;
forn(i,n) {
  int x = a[i];
  f[x]++;
  ans = max(ans, 1ll*x*f[x]);
  b[i] = ans;
}

In the end, b[r] holds the answer to the query on [0,r].

→ Ответить

Indiot

10 месяцев назад, # ^ |

the original requires update operation sadly, but thank u for spending precious time implement this!

→ Ответить

AvaraKedavra

10 месяцев назад, # |

← Rev. 7 →

To be able to get the hell out of this grey color, i'm learning new data structures

I wonder why no one pointed at this. To get out of grey color, you don't need to learn advanced data structures like Fenwick tree. Start with problems of rating 800 (if you are a newbie), solve 50-100 problems of 800 rating, then move to problems of rating 900,1000,1100....in a similar manner. Make sure you have sorted the problems in decreasing order of number of people who have solved it.

I am currently solving 1300 rating problems and haven't used anything fancy data structures/algorithms till now (like DFS,BFS,Dijkstra,DP etc). Forget about using Fenwick trees.

Also, focus on Div3 rated contests at this stage. It will help you increase your ratings. All the best !

→ Ответить

comingsoon.cpp

10 месяцев назад, # ^ |

← Rev. 4 →

Is my practice strategy good?

→ Ответить

AvaraKedavra

10 месяцев назад, # ^ |

Yeah, its good. You need to practice problems related to topics you have learnt. Solving 100 problems related to every topic is an overkill imo. There are so many topics out there. It will be very time consuming.

Also, if you want to increase your ratings faster, you should do what I wrote above.

→ Ответить

Medeali

10 месяцев назад, # |

← Rev. 2 →

really learning fenwick tree to get out of grey the tree is not needed until you want to reach exepert or even more sometimes dude go focus on solving B's,btw i still don't understand how you got to specialist unless your level magically got down

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 22.11.2024 13:26:52 (i2).

Десктопная версия, переключиться на мобильную.

При поддержке