The general rule is: don't worry too much about such micro optimizations. Internally the program might have to follow a few more pointers, but not many, so your program might be <1% slower. And the odds are good that the compiler will even eliminate those overhead and you have the exact same speed.

I prefer using OOP while implementing data structures.

There are some reasons behind this:

1. You can create multiple instances of your object. There are some problems where you may create, for example, more than one Fenwick tree. It's much easier to implement it if you have Fenwick tree as a class.

2. It may also decrease the amount of code. I remember a problem where I needed two segment trees with different operations. You need to implement it once if you put it into a class. Also this class can be made template.

3. The code looks much simpler and cleaner.

4. Classes are better when re-using code (it's helpful when you can use pre-written code on contests).

The disadvantages you noticed doesn't matter much:

1. Code speed. If you write on C++, the perfomance is nearly identical (maybe slower, maybe faster) to the implementation without OOP.

2. Typing speed. It doesn't take much to write this, isn't it?

class Klass {
private:

public:

};

That's all the overhead. If you care much, you can configure your editor to generate this template automatically.

Besides, I never write treaps in OOP style (only struct Treap + functions). It's more convenient for me.