# sum selected nodes of a set in $\log n$ time

Given a sum operation of a dynamic set $$S$$ of length $$n$$ which includes integer pairs $$(x, y)$$. The sum operation is defined as taking two inputs $$a$$ and $$b$$ such that $$a \leq b$$. The sum operation should return the sum of y values of all pairs $$(x, y)$$ such that $$a \leq x \leq b$$ in $$\log n$$ time.

My goal is to come up with a data structure that supports the operation described above.

My attempt: If we need the operation in $$\log n$$ time, we definitely need a self-balanced tree. In this problem, I choose splay-tree. The amortized complexity of splay-tree for insert, search, and delete are all in $$\log n$$ time. Is the amortized complexity of sum operation in $$\log n$$ as well? If yes, how can we prove this?

• If we need the operation in $\log n$ time, we definitely need a self-balanced tree. Not really. While you can solve this using balanced trees, under some conditions the natural solutions are segment trees or Fenwick trees. Is the amortized complexity of sum operation in $\log n$ as well. You didn't describe how to implement sum. – user114966 Oct 14 '20 at 21:54