2

Binary Indexed Tree
* Point Update & Range Query                |  * Range Update & Range Query            |   * Inversion Count
  int res[MAXN], N;                         |    int res_1[MAXN];   // BIT 1           |    1. UPDATE FUNCTION
  void UPDATE(int idx, int val) {           |    void UPDATE_1(int idx, int val) {     |    2. READ FUNCTION
   	  while (idx <= N) {					|		while (idx <= N) {                 |   // map all number w.r first index
		  res[idx] += val;                  |        	res_1[idx] += val;             |   for (int i = 0; i < N; i++) {
		  idx += (idx & -idx);              |           idx += (idx & -idx);           |        cin >> A[i];
	  }                                     |       }                                  |        B[i] = A[i];
  }                                         |   }                                      |   }
  int READ(int idx) {                       |   int READ_1(int idx) {                  |   sort(B, B+N);
	  int sum = 0;                          |   	int sum = 0;                       |   for (int i = 0; i < N; i++) {
	  while (idx > 0) {                     |       while (idx > 0) {                  |       int rank = lower_bound(B, B+N, A[i])-B;
		  sum += res[idx];                  |       	sum += res_1[idx];             |       rank += 1;  // BIT is 1 indexed
		  idx -= (idx & -idx);              |           idx -= (idx & -idx);           |       A[i] = rank;
	  }                                     |       }                                  |   }
	  return sum;                           |       return sum;                        |   ll inversion = 0;
  }                                         |    }                                     |   for (int i = N-1; i >= 0; i--) {
  int QUERY(int l, int r) {                 |    int res_2[MAXN];     // BIT 2         |       int x = READ(A[i]-1);
   	  return READ(r) - READ(l-1);           |    void UPDATE_2(int idx, int val) {     |       inversion += x;
  }                                         |    	while (idx <= N) {                 |       update(A[i]);
* Range Update & Point Query                |       res_2[idx] += val;                 |   }
  void UPDATE(int idx, int val) {           |       idx += (idx & -idx);               |_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
	  while (idx <= N) {                    |       }
		  res[idx] += val;                  |    }
		  idx += (idx & -idx);              |    int READ_2(int idx) {
	  }                                     |    	int sum = 0;
  }                                         |    	while (idx > 0) {
  void RANGE_UPDATE(int l, int r, int val) {|       	sum += res_2[idx];
	  UPDATE(l, val);                       |           idx -= (idx & -idx);
	  UPDATE(r+1, -val);                    |           }
  }                                         |           return sum;
  int QUERY(int idx) {                      |     }
	  int sum = 0;                          |     void RANGE_UPDATE(int l, int r, int val) {
	  while (idx > 0) {                     |      	 UPDATE_1(l, val); UPDATE_1(r+1, -val);
		  sum += res[idx];                  |        UPDATE_2(l, val*(l-1)); UPDATE_2(r+1, -val*r);
		  idx -= (idx & -idx);              |     }
	  }                                     |     int RANGE_QUERY(int l, int r) {
	  return sum;                           |     	 int sum_r = READ_1(r)*r - READ_2(r);
  }                                         |        int sum_l = READ_1(l-1)*(l-1) - READ_2(l-1);
                                            |        return sum_r - sum_l;