mog project: 2012.02

2.28.2012

Binary Indexed Tree (BIT) in C++

C++: BITの実装

BITは、数列においてある区間の合計値を効率良く求めたい場合などに使われるデータ構造である。
計算量は、値の加算、合計値の取得ともにO(log n)。

0-indexed にて実装してみる。

//------------------------------------------------------------------------------
// Binary Indexed Tree (BIT)
//------------------------------------------------------------------------------
template <typename T>
class BinaryIndexedTree {
 public:
  BinaryIndexedTree(int size) : size_(size) {
    data_.resize(size + 1);
  }
  void Add(int index, T value) {
    if (index < 0 || index >= size_) return;
    ++index;
    while (index <= size_) {
      data_[index] += value;
      index += index & -index;
    }
  }
  T Sum(int index) {
    if (index < 0 || index >= size_) return 0;
    ++index;
    T ret = 0;
    while (index > 0) {
      ret += data_[index];
      index -= index & -index;
    }
    return ret;
  }
 private:
  std::vector<T> data_;
  int size_;
};

2.22.2012

Handling XML with VBScript

VBScript で XML を扱う

「Msxml2.DOMDocument」オブジェクトを利用すれば、VBScript で効率化に XML を扱うことができる。
詳細は後日投稿予定。

・Microsoft リファレンス
http://msdn.microsoft.com/en-us/library/windows/desktop/ms762722%28v=vs.85%29.aspx

2.13.2012

Determinant of a square matrix in C++

C++: 行列式の計算

メモ。

http://paulbourke.net/miscellaneous/determinant/
http://thira.plavox.info/blog/2008/06/_c.html
http://www.softwareandfinance.com/CPP/Matrix_Determinant.html
http://cboard.cprogramming.com/cplusplus-programming/30001-determinant-calculation.html

2.06.2012

How to split a string with space in C++

C++: 文字列をスペースで分割

文字列を区切ってベクタに代入するエレガントな方法。

・コード

#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <iterator>

//------------------------------------------------------------------------------
// Split a string with space
//------------------------------------------------------------------------------
std::vector<std::string> split(std::string const& s) {
  std::istringstream iss(s);
  return std::vector<std::string>(
      std::istream_iterator<std::string>(iss),
      std::istream_iterator<std::string>());
}

int main() {
  std::vector<std::string> a = split("a dramatic turn of events");
  std::vector<std::string> b = split("1 23 456 7890");

  for (int i = 0; i < (int)a.size(); ++i) { std::cout << a[i] << std::endl; }
  for (int i = 0; i < (int)b.size(); ++i) { std::cout << b[i] << std::endl; }

  return 0;
}

・出力