# Simple efficient algorithm for dynamically maintaining max of special linear functions

Given $$n$$ tuples $$(k_i >0,a_i >0)$$, is there any efficient algorithm that can dynamically track $$\max_{i=1,\cdots,n} \left\{k_i\left(\sum_{j=1}^n a_j\right) - a_i\right\}$$ in response to online updates to $$a_i$$? (in $$\text{poly}(\log n)$$ complexity per update).

I do have an algorithm in mind, which sees $$k_i$$s as the slope of lines and $$-a_i$$s as intercepts. The problem then can be reduced to maintaining the upper envelope of $$n$$ lines, which can be further reduced to a dynamic planar convex hull problem with established algorithm giving $$\mathcal O(\log^2n)$$ worst-case complexity per update.

I am not satisfied by my reduction because it ignores many specific structure of the problem that may be exploited. In addition, because I need to actually implement this algorithm in my project, a solution with dynamic convex hull is just way too tedious. Are there simpler algorithms for this problem with comparable complexity?

• what is the desired space complexity? Sep 11 at 6:52
• @InuyashaYagami I expect $n$ to be on the order of $10^5$ to $10^6$ so a space complexity of $\mathcal O(n \log n)$ or $\mathcal O(n \log^2 n)$ would be reasonable. $\mathcal O(n \sqrt n)$ would be acceptable too if that's necessary. Sep 11 at 12:58