Submission #3564850

Source Code Expand

#include "variance.h"
#include <vector>
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
using namespace std;
typedef long long ll;

template<typename T>
struct BIT {
  vector<T> data;
  BIT(int n) {
    int sz = 1;
    while(sz < n) sz <<= 1;
    data.assign(sz+1, 0);
  }
  T sum(int ed) const {
    T res(0);
    for(; ed > 0; ed &= ed-1) res += data[ed];
    return res;
  }
  T sum(int bg, int ed) const { return sum(ed) - sum(bg); }
  void add(int i, const T& x) {
    for(++i; i < (int)data.size(); i += i & -i) data[i] += x;
  }
};


int N;
int *A;
BIT<ll> ex(0);
BIT<ll> ex2(0);


void init(int n, int *a) {
  ex = BIT<ll>(n);
  ex2 = BIT<ll>(n);
  REP(i, n){
    ex.add(i, a[i]);
    ex2.add(i, a[i]*a[i]);
  }
  N = n;
  A = a;
  
}
int variance(int i, int j) {
  double k = j - i + 1;
  double tmp = ex.sum(i, j+1) / k;
  return (int)(ex2.sum(i, j+1)/k - tmp*tmp);
}
void update(int i, int x_) {
  ll x = x_;
  ex.add(i, x - A[i]);
  ex2.add(i, x*x - A[i]*A[i]);
  A[i]=x;
}

Submission Info