#include<bits\stdc++.h>
using namespace std;
#define int long long


struct node
{
	int sum=0;
	int arr[41] = { 0 };
	node(int x = 0) {
		arr[x] = 1;
		sum = 0;
	}

};
node out()
{
	return node(0);
}
node proces(node a, node b)
{
	node c;
	c.sum = a.sum + b.sum;
	int sum = 0;;
	for (int i = 1; i <= 40; i++)
	{
		c.arr[i] = a.arr[i] + b.arr[i];
		c.sum += sum*a.arr[i];
		sum += b.arr[i];
	}
	return c;
}
int const nn = 4e5 + 1;
int n;
int a1[nn];
node tree1[nn];
void build_tree(node *tree, int *a, int s, int e, int ind)
{
	if (s == e)
	{
		tree[ind] = node(a[s]);
		return;
	}
	int mid = (s + e) / 2;
	build_tree(tree, a, s, mid, ind * 2);
	build_tree(tree, a, mid + 1, e, (ind * 2) + 1);
	tree[ind] = proces(tree[ind * 2], tree[(ind * 2) + 1]);
	return;
}
node query(node *tree, int ss, int se, int qs, int qe, int ind)
{
	//complete overlap
	if (ss >= qs && se <= qe)
		return tree[ind];

	// no overlap
	if (qe<ss || qs>se)
		return out();
	int mid = (ss + se) / 2;
	node left = query(tree, ss, mid, qs, qe, ind * 2);
	node right = query(tree, mid + 1, se, qs, qe, ind * 2 + 1);
	return proces(left, right);

}
void update(node *tree, int ss, int se, int i, int new_val, int ind)
{
	//case where the I is out of bound 
	if (i > se || i < ss)
		return;

	// leaf node 
	if (ss == se)
	{
		tree[ind] = node(new_val);
		return;
	}
	//otherwise 
	int mid = (ss + se) / 2;
	update(tree, ss, mid, i, new_val, ind * 2);
	update(tree, mid + 1, se, i, new_val, ind * 2 + 1);

	tree[ind] = proces(tree[ind * 2], tree[ind * 2 + 1]);
	return;
}

int32_t main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a1[i];
	build_tree(tree1, a1, 1, n, 1);
	while (m--)
	{
		int ty;
		cin >> ty;
		if (ty == 1)
		{
			int x, y;
			cin >> x >> y;
			node num = query(tree1, 1, n, x, y, 1);
			cout << num.sum << endl;
		}
		else {
			int ind, v;
			cin >> ind >> v;
			update(tree1, 1, n, ind, v, 1);
		}

	}
}