Submission #3422665

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
#include "variance.h"
 
const int MAX_BIT = 1 << 17;
 
typedef long long ll;
 
struct BIT {
  int n;
  ll bits[MAX_BIT + 1];
 
  //BIT() { bzero(bits, sizeof(ll) * (MAX_BIT + 1)); }
  
  void init(int _n) { n = _n; }
 
  ll sum(int x) {
    ll s = 0;
    while (x > 0) {
      s += bits[x];
      x -= (x & -x);
    }
    return s;
  }
 
  void add(int x, ll v) {
    while (x <= n) {
      bits[x] += v;
      x += (x & -x);
    }
  }
};
 
int N, A[MAX_BIT];
 
BIT ais, ai2s;
 
void init(int n, int *a) {
  N = n;
 
  ais.init(n);
  ai2s.init(n);
  
  for (int i = 0; i < N; i++) {
    A[i] = a[i];
    ais.add(i + 1, A[i]);
    ai2s.add(i + 1, A[i] * A[i]);
  }
}
 
int variance(int i, int j) {
  ll suma = ais.sum(j + 1) - ais.sum(i);
  ll suma2 = ai2s.sum(j + 1) - ai2s.sum(i);
  ll k = j + 1 - i;
  //printf("v(%d,%d): suma=%lld, suma2=%lld\n", i, j, suma, suma2);
  
  ll v = (k * suma2 - suma * suma) / (k * k);
  return (int)v;
}
 
void update(int i, int x) {
  ll da = x - A[i], da2 = x * x - A[i] * A[i];
  A[i]=x;
  ais.add(i + 1, da);
  ai2s.add(i + 1, da2);
}

Submission Info