We have to maintain an array $ a_1,\ldots,a_n$ supporting the following operations:

- Assign $ a_i = x$
- Given $ \ell,r$ , return $ \sum_{i=\ell}^r a_i$
- Given $ \ell,r$ , return $ \sum_{i=\ell}^r \sum_{j=\ell}^r a_i a_j$
- Given $ \ell,r$ , return $ \sum_{i=\ell}^r \sum_{j=\ell}^r \sum_{k=\ell}^r a_i a_j a_k$

After $ O(n)$ initialization, these operations should run in amortized $ O(\log n)$ time.