Stupid question on Fenwick Tree

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
34:20:17
Register now »

*has extra registration

→ Top rated

#	User	Rating
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

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
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

View all →

→ Find user

→ Recent actions

Detailed →

Indiot's blog

Stupid question on Fenwick Tree

By Indiot, history, 10 months ago, In English

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 months ago
16

Comments (16)

Write comment?

VMaksimoski008

10 months ago, # |

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

→ Reply

Indiot

10 months ago, # ^ |

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

→ Reply

VMaksimoski008

10 months ago, # ^ |

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

→ Reply

Indiot

10 months ago, # ^ |

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)

→ Reply

Indiot

10 months ago, # ^ |

← Rev. 2 →

that's my fault to be honest

edit: never mind, i solved the problem

→ Reply

VMaksimoski008

10 months ago, # ^ |

How did you solved the problem?

→ Reply

Indiot

10 months ago, # ^ |

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

→ Reply

Papercut

10 months ago, # |

← 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)

→ Reply

Indiot

10 months ago, # ^ |

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

→ Reply

vstiff

10 months ago, # ^ |

← Rev. 2 →

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

→ Reply

estoy-re-sebado

10 months ago, # |

← 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].

→ Reply

Indiot

10 months ago, # ^ |

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

→ Reply

AvaraKedavra

10 months ago, # |

← 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 !

→ Reply

comingsoon.cpp

10 months ago, # ^ |

← Rev. 4 →

Is my practice strategy good?

→ Reply

AvaraKedavra

10 months ago, # ^ |

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.

→ Reply

Medeali

10 months ago, # |

← 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

→ Reply