Запрос разных сумм на отрезке

У меня есть массив a1, a2, . . . , an и мне нужно обработать несколько типов запросов, всего запросов - q
а) по числам pos и x выполнить присваивание a[pos] := x;
б) по числам l и r вывести sum ai, где l≤i≤r то есть, al + ... + ar
в) по числам l и r вывести sum ai * aj, где l≤i≤j≤r то есть, al * al + al * a(l + 1) + ... + ar*ar
г) по числам l и r вывести sum ai * aj * ak, где l≤i≤j≤k≤r то есть, al* al * al + al *al * a(l + 1) + ... + ar * ar * ar

Мне нужно всё это выполнять за O(n + qlogn)