3

(Okay, so my previous question is on hold as being too broad, so I'm narrowing it down here.)

I'm looking to take part in algorithmic programming contests, and a lot of problems hinge on the use of specialized data structures which are extremely good at a certain operation - for example, Fenwick trees allow calculation of prefix sums of a list of values in logarithmic time.

What is the preferred way of implementing such data structures in modern C++ (i.e. using C++11 features)? Is it possible to use STL algorithms and containers instead of writing structs and coding every operation by hand?

I'm looking for Fenwick trees, segment trees, treaps and some other data structures often useful in IOI-style contests, but general strategies are more than enough.

Soham Chowdhury
  • 2,125
  • 2
  • 18
  • 29
  • 2
    Why do you put special emphasis on modern C++? What new language construct or standard library enhancement do you have in mind that would make a difference? – Peter - Reinstate Monica Dec 15 '14 at 11:25
  • @PeterSchneider I may be wrong, but as far as I know C++11 introduces a lot of new STL algorithms that make some things easier, such as [some shown here](http://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c). – Soham Chowdhury Dec 15 '14 at 11:29
  • @PeterSchneider my point was that answers should preferably exploit everything C++11 has to offer. – Soham Chowdhury Dec 15 '14 at 11:31

1 Answers1

3

there's an implementation of a fenwick tree here: http://www.algorithmist.com/index.php/Fenwick_tree

It uses std::vector as the underlying container. arguably the method increase could be written in terms of std::transform or std::foreach.

Richard Hodges
  • 68,278
  • 7
  • 90
  • 142