Consider a segment tree “tree” where all nodes hold some matrix. Like I said in my previous comment, let us store in the leaf node, M^x where x is the corresponding element and M = [[1,1],[1,0]].

Now for a node which is not a leaf, we simply need tree + tree[right] + tree.tree[right], where left and right are the left and right child respectively. We keep doing this recursively and build the segment tree.

Now for updating, we will update only one element and not a range. So we update a leaf node, and make sure to update all the ancestors of this leaf node. In other words, we are rebuilding the segment tree for every update. Also note, after using the array element initially to build the segment tree, the array is not needed anywhere else in the code. So actually when updating the array, we can only update the segment tree because all further computations will be held by the segment tree.

For query, I followed the basic segment tree propagation method (not lazy) to create a dummy matrix which will hold the data for the range query. This matrix will contain the final result. We only output the [1][0] element of this matrix. For further details, please read my code here and my earlier post. Cheers!