0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Dmitry Oct 14 '20 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.