#include <bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define LagaKar ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mp make_pair
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ook order_of_key   //number of elements less than k
#define fbo find_by_order  //k th element
#define nline "\n"
#define YES cout<<"YES"<<nline
#define NO cout<<"NO"<<nline
#define Yes cout<<"Yes"<<nline
#define No cout<<"No"<<nline
#define precise(ans)  cout<<fixed<<setprecision(15)<<ans
#define fo(i,n) for(ll i=0;i<n;i++)
#define Fo(i,k,n) for(ll i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define sz(x) ((ll)(x).size())
#define all(x) x.begin(), x.end()
#define MAX(x) *max_element(all(x))
#define MIN(x) *min_element(all(x))
#define SUM(x) accumulate(all(x), 0LL)
#define CNT(x) __builtin_popcountll(x)
typedef long long ll; typedef unsigned long long ull; typedef long double lld;
template <typename T> using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T, typename R> using o_map = tree<T, R, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef pair<ll, ll>  pl;   typedef vector<ll>  vl;typedef vector<vl>  vvl;
typedef vector<pl>  vpl;    template <typename T> using prq_mx  = priority_queue<T>;
template <typename T> using prq_mn = priority_queue<T, vector<T>, greater<T>>;
#ifdef hydracody
    #include <C:\Users\Anurag Dwivedi\Desktop\cpc\debug.h>
#else
#define debug(x)
#endif
const double eps=1e-9;const ll INF=(ll)1e9;const ll inf64=2e18;const ll INF64=9e18;
#define PI 3.1415926535897932384626
#define MOD 1000000007
#define MOD1 998244353
#define MOD2 1000000009

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ll power(ll x,ll y, ll p){if(y==0)return 1;ll res = 1;x = x % p;if (x == 0) return 0;while (y > 0){if (y & 1)res = (res*x) % p;y = y>>1;x = (x*x) % p;}return res;}
ll pinv(ll a, ll m){ return power(a, m - 2, m); }
ll int_sqrt (ll x) {ll ans = 0; for (ll k = 1LL << 30; k != 0; k /= 2) {if ((ans + k) * (ans + k) <= x) {ans += k;}} return ans;}
ll logceil(ll x){ll s=0;while(x>0){s++;x=x/2;}return s;}
ll mod_add(ll a, ll b,ll mod) {
    a = a % mod; b = b % mod;
    return (((a + b) % mod) + mod) % mod;
}
ll mod_mul(ll a, ll b,ll mod) {
    a = a % mod; b = b % mod;
    return (((a * b) % mod) + mod) % mod;
}
ll mod_sub(ll a, ll b,ll mod) {
    a = a % mod; b = b % mod;
     return (((a - b) % mod) + mod) % mod;
}

/////////////////////////////////////////////////////////////////////////////////////////////////
/*Don't loss hope, one day you will make it. Till then work hard.
One day these bad days will go and you will rock.*/





struct node{
  vector<ll> cc=vector<ll>(45,0);
  ll count=0;
};

struct Segtree {
  vector<node> t;
  Segtree(ll n) {
    t.resize(4*n);
  }
  void build(vector<ll>& a,ll n, ll b, ll e) {
    if (b == e) {
      t[n].cc[a[b]] =1;
      t[n].count=0;
      return;
    }
    ll mid = (b + e) >> 1, l = n << 1, r = l | 1;
    build(a,l, b, mid);
    build(a,r, mid + 1, e);
    t[n].count=t[l].count +t[r].count;
    for(ll i=40;i>0;i--){
      ll s=0;
      for(ll j=i+1;j<40;j++){
        s+=t[l].cc[j];
      }
      t[n].count+=t[r].cc[i]*s;
      t[n].cc[i]=t[l].cc[i]+t[r].cc[i];
    }

  }
  void update(ll n, ll b, ll e, ll i, ll x) {
    if (b > i || e < i) return;
    if (b == e && b == i) {
      // t[n]= (b%2==0? x:-x);
      for(ll j=1;j<41;j++){
        t[n].cc[j]=0;
      }
      t[n].cc[x]=1;
      return;
    }
    ll mid = (b + e) >> 1, l = n << 1, r = l | 1;
    update(l, b, mid, i, x);
    update(r, mid + 1, e, i, x);
    t[n].count=t[l].count +t[r].count;
    for(ll i=40;i>0;i--){
      ll s=0;
      for(ll j=i+1;j<40;j++){
        s+=t[l].cc[j];
      }
      t[n].count+=t[r].cc[i]*s;
      t[n].cc[i]=t[l].cc[i]+t[r].cc[i];
    }
  }
  node query(ll n, ll b, ll e, ll i, ll j) {
    if (b > j || e < i) return node();
    if (b >= i && e <= j){
      return t[n];
    }
    ll mid = (b + e) >> 1, l = n << 1, r = l | 1;
    node L = query(l, b, mid, i, j);
    node R = query(r, mid + 1, e, i, j);
    node ans;
    ans.count=L.count +R.count;
    for(ll i=40;i>0;i--){
      ll s=0;
      for(ll j=i+1;j<40;j++){
        s+=L.cc[j];
      }
      ans.count+=R.cc[i]*s;
      ans.cc[i]=L.cc[i]+R.cc[i];
    }
    return ans;
  }
};
/*
[i,j]
Segtree s(n);
s.build(1,0,n-1);
s.update(1,0,n-1,l,val);
s.query(1,0,n-1,l,r);
*/





void  chal(){
  ll n,m;
  cin>>n>>m;
  vl aa(n);
  fo(i,n){
    cin>>aa[i];
  }
  Segtree s(n);
  s.build(aa,1,0,n-1);
  fo(i,m){
    ll ty;
    cin>>ty;
    if(ty==1){
      ll l,r;
      cin>>l>>r;
      l--;r--;
      cout<<s.query(1,0,n-1,l,r).count<<nline;
    }else{
      ll l,val;
      cin>>l>>val;
      l--;
      s.update(1,0,n-1,l,val);
    }
  }





















}




//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
int32_t main() {
  LagaKar;
#ifdef hydracody
  freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); freopen("error.txt", "w", stderr);
#endif
  ll  t; t = 1;
  // cin>>t;
  for (ll i = 1; i <= t; i++) {
    // cerr<<"Case : "<<i<<endl;
    // cout<<"Case #"<<i<<": ";
    chal();
  }
  return 0;
}