[toph.co] Playing With BITs

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Playing With BITs
Source            : toph.co
Category          : Data Structure
Algorithm         : Segment Tree
Verdict           : Accepted

#include <bits/stdc++.h>
 
using namespace std;
 
static const int maxn = 1e5 + 5;
 
#define ll           long long
 
struct segmentTree
{
      int bit[62];
      inline void assignLeaf(ll num)
      {
            for (int k = 0; k < 61; k++)
                  bit[k] = (bool)(num & (1LL << k));
      }
      inline void marge(segmentTree &L, segmentTree &R)
      {
            for (int k = 0; k < 61; k++)
                  bit[k] = L.bit[k] + R.bit[k];
      }
      inline int kthSet(int k)
      {
          return bit[k];
      }
} tree[maxn << 2];
 
ll arr[maxn];
 
inline void build(int node, int a, int b)
{
      if (a == b)
      {
            tree[node].assignLeaf(arr[a]);
            return;
      }
      int lft = node << 1;
      int rgt = lft | 1;
      int mid = (a + b) >> 1;
      build(lft, a, mid);
      build(rgt, mid+1, b);
      tree[node].marge(tree[lft], tree[rgt]);
}
 
inline void update(int node, int a, int b, int pos, ll num)
{
      if (a > b or a > pos or b < pos) return;
      if (a >= pos && b <= pos)
      {
            tree[node].assignLeaf(num);
            return;
      }
      int lft = node << 1;
      int rgt = lft | 1;
      int mid = (a + b) >> 1;
      update(lft, a, mid, pos, num);
      update(rgt, mid+1, b, pos, num);
      tree[node].marge(tree[lft], tree[rgt]);
}
 
inline segmentTree QUERY(int node, int a, int b, int i, int j)
{
      if (a > b || a > j || b < i)
      {
            segmentTree null;
            fill(begin(null.bit), end(null.bit), 0);
            return null;
      }
      if (a >= i && b <= j) return tree[node];
      int lft = node << 1;
      int rgt = lft | 1;
      int mid = (a + b) >> 1;
      segmentTree p1, p2, res;
      p1 = QUERY(lft, a, mid, i, j);
      p2 = QUERY(rgt, mid+1, b, i, j);
      res.marge(p1, p2);
      return res;
}
 
int main()
{
      //freopen("in.txt", "r", stdin);
 
      int n;
      scanf("%d", &n);
      for (int i = 1; i <= n; i++) scanf("%lld", &arr[i]);
      build(1, 1, n);
      int q;
      scanf("%d", &q);
      while (q--)
      {
            int type;
            scanf("%d", &type);
            if (type == 1)  // update
            {
                  int pos;
                  ll num;
                  scanf("%d %lld", &pos, &num);
                  update(1, 1, n, pos, num);
            }
            else
            {
                  int l, r, k;
                  scanf("%d %d %d", &l, &r, &k);
                  segmentTree res = QUERY(1, 1, n, l, r);
                  printf("%d\n", res.bit[k]);
            }
      }
}