Stupid question on Fenwick Tree
source link: https://codeforces.com/blog/entry/124811
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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!
2 weeks 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 |
-
Hey, thanks for your detailed response! Actually the original problem requires update operation (add / remove element). So here is my code:
codeBut it does not give the right answer, where am I missing here? tks again
-
You didn't specify that the problem has updates, so I thought you only have to answer queires. Sorry.
-
full code
Original problem (japanese)
-
-
Fun fact: Fenwick tree does not support non-invertible operations, that is, it's impossible to calculate v[l]∘v[l+1]∘…∘v[r]v[l]∘v[l+1]∘…∘v[r] for an arbitrary l,rl,r if ∘∘ is max/min/gcdmax/min/gcd etc. (however, we can support something like: 1) calculate minimum value among v[l..r]v[l..r] 2) decrease v[i]v[i] by xx) So, in general, your problem is not solvable with single Fenwick tree (but the comment above describes a decent solution). |
You don't need Fenwick tree here, just
In the end, |
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 ! |
-
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? :)
-
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.
-
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK