Stupid question on Fenwick Tree

→ Pay attention

Contest is running
Codeforces Round 942 (Div. 1)
00:34:21

Contest is running
Codeforces Round 942 (Div. 2)
00:34:21

→ Streams

CodeChef Starters 132 Solution Discussion

By aryanc403

Before stream 24:14:21

View all →

→ Top rated

#	User	Rating
1	ecnerwala	3649
2	Benq	3581
3	jiangly	3578
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	tourist	3565
8	maroonrk	3531
9	Radewoosh	3521
10	Um_nik	3482

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	maomao90	174
2	awoo	165
3	adamant	161
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	orz	146
8	SecondThread	146
10	pajenegod	145

View all →

→ Find user

→ Recent actions

Detailed →

Indiot's blog

Stupid question on Fenwick Tree

By Indiot, history, 3 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
3 months ago
16

Comments (16)

Write comment?

VMaksimoski008

3 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

3 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

3 months ago, # ^ |

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

→ Reply

Indiot

3 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

3 months ago, # ^ |

← Rev. 2 →

that's my fault to be honest

edit: never mind, i solved the problem

→ Reply

VMaksimoski008

3 months ago, # ^ |

How did you solved the problem?

→ Reply

Indiot

3 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

3 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

3 months ago, # ^ |

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

→ Reply

vstiff

3 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

3 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

3 months ago, # ^ |

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

→ Reply

AvaraKedavra

3 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

3 months ago, # ^ |

← Rev. 3 →

I'm currently self leaning maths from scratch (Pre algebra) and I'm currently in some basic geometry in algebra 1. I've almost solved every 800 rated problem tagged (geometry). What do you think of this approach to learning CP? :)

→ Reply

AvaraKedavra

3 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

3 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