如何使用二叉树在log（n）时间复杂度中获取堆栈的部分求和

问：

我几乎完成了自定义数据结构，但我被困在最后一个功能上，因为我几乎没有使用树的经验。我需要添加一个函数，该函数可以获取堆栈中前 k 个元素的总和。例如，在堆栈 [1， 2， 3， 4， 5] 中，前 3 个元素的总和为 5+4+3 = 12。这一切都需要符合 log（n） 时间复杂度或尽可能接近。这应该通过创建一个二叉树来实现，该二叉树的叶子是堆栈中的元素，父树是其 2 个子树的总和。下面是树应该是什么样子的示例

                           38
                         /    \
                       21     17
                      /  \   /  \
                     13   8 10   7    

我需要能够将元素设置为新值，并且只能从前面添加或删除值，因为“主要”数据存储在堆栈中。

我有一个使用常规 arrayList 实现它，但它的运行时是 O（n） 而不是所需的 O（log（n））

public long ksum(int k) {
    long sum = 0;
    for(int i=0; i<k && i<ds.size(); i++)
      sum += ds.get(ds.size() - 1 - i);
    return sum;
  }

这是我目前所拥有的全部代码。将对 push、pop 和 set 等函数进行更改，以更新数据结构以及 ksum 函数本身

import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.TreeMap;

public class UltraFast implements UltraStack {
    protected Stack<Integer> stack;
    protected PriorityQueue<Integer> maxHeap;

    public UltraFast() {
        stack = new Stack<>();
        maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
    }

    public void push(int x) {
        stack.push(x);
        maxHeap.offer(x);

    }

    public Integer pop() {
      if (stack.isEmpty()) {
          return null;
      }
      int top = stack.pop();
      maxHeap.remove(top);


      return top;
  }
  

    public Integer set(int i, int x) {
        if (i < 0 || i >= stack.size())
            return null;

        int oldValue = stack.get(i);
        stack.set(i, x);

        maxHeap.remove(oldValue);
        maxHeap.offer(x);

        return oldValue;
    }

    public long ksum(int k) {
      //code here
      return null;
  }
  
  

    public Integer get(int i) {
      if (i < 0 || i >= stack.size())
        return null;
        return stack.get(i);
    }

    public Integer max() {
      if (maxHeap.isEmpty()) {
         return null;
      }
      return maxHeap.peek();
    }

    public int size() {
        return stack.size();
    }

    public Iterator<Integer> iterator() {
        return stack.iterator();
    }
    
    
}