Indexed Tree with template
구현2017. 3. 22. 14:38
#include <cstdio>
#include <functional>
using namespace std;
template <typename _T>
class IndexedTree {
private:
size_t m;
_T *A;
function<_T(const _T &, const _T &)> F;
public:
IndexedTree(size_t n, function<_T(const _T &, const _T &)> f) {
for (m = 1; m < n; m <<= 1);
A = new _T[m << 1];
F = f;
}
void Update(size_t idx, _T val) {
idx |= m;
A[idx] = val;
while (idx >>= 1) A[idx] = F(A[idx << 1], A[idx << 1 | 1]);
}
_T Query(size_t L, size_t R) {
_T Lval = _T(), Rval = _T();
L |= m;
R |= m;
while (L <= R) {
if (L & 1) Lval = F(Lval, A[L++]);
if (!(R & 1)) Rval = F(A[R--], Rval);
L >>= 1;
R >>= 1;
}
return F(Lval, Rval);
}
};
int a[10] = { 6, 2, 3, 8, 4, 5, 1, 9, 7, 10 };
int main() {
IndexedTree<int> IT(10, [](auto u, auto v) { return u + v; });
for (int i = 0; i < 10; i++) IT.Update(i, a[i]);
printf("%d %d : %d\n", 2, 6, IT.Query(2, 6));
printf("%d %d : %d\n", 3, 8, IT.Query(3, 8));
return 0;
}
'구현' 카테고리의 다른 글
| Stable Radix Sort (0) | 2016.10.21 |
|---|
Stable Radix Sort
구현2016. 10. 21. 14:32
A[0..N-1]들을 B[A[i]] 오름차순으로 정렬하여 C[0..N-1]에 넣는다. (B[A[i]]들은 0 이상 M 이하의 정수)
만약 B[A[i]]의 값이 같다면 A에서 먼저 나온 순서대로 넣는다.
#include <cstdio>
const int MAXM = 10;
int D[MAXM + 1];
void radixSort(const int *A, const int *B, int *C, int N, int M) {
int i;
for (i = 0; i <= M; i++) D[i] = 0;
for (i = 0; i < N; i++) D[B[A[i]]]++;
for (i = 1; i <= M; i++) D[i] += D[i - 1];
for (i = N; i--; C[--D[B[A[i]]]] = A[i]);
}
int A[10] = { 5, 0, 3, 7, 4, 1, 9, 8, 2, 6 };
int B[10] = { 3, 4, 3, 2, 1, 1, 4, 2, 3, 1 };
int R[10];
int main() {
int i;
radixSort(A, B, R, 10, 4);
for (i = 0; i < 10; i++) printf("%d %d %d\n", i, R[i], B[R[i]]);
}
with vector
#include <cstdio>
#include <vector>
using namespace std;
void radixSort(const vector<int> &A, const vector<int> &B, vector<int> &C, int N, int M) {
int i;
vector<int> D(M + 1, 0);
for (i = 0; i <= M; i++) D[i] = 0;
for (i = 0; i < N; i++) D[B[A[i]]]++;
for (i = 1; i <= M; i++) D[i] += D[i - 1];
for (i = N; i--; C[--D[B[A[i]]]] = A[i]);
}
vector<int> A({ 5, 0, 3, 7, 4, 1, 9, 8, 2, 6 });
vector<int> B({ 3, 4, 3, 2, 1, 1, 4, 2, 3, 1 });
vector<int> R(10);
int main() {
int i;
radixSort(A, B, R, 10, 4);
for (i = 0; i < 10; i++) printf("%d %d %d\n", i, R[i], B[R[i]]);
}
with template
#include <cstdio>
#include <vector>
using namespace std;
template <typename _RanItA, typename _RanItB>
void radixSort(_RanItA _AFirst, _RanItA _ALast, _RanItB _B, _RanItA _C, int M) {
_RanItA _A;
int i;
vector<int> D(M + 1, 0);
for (i = 0; i <= M; i++) D[i] = 0;
for (_A = _AFirst; _A != _ALast; _A++) D[_B[*_A]]++;
for (i = 1; i <= M; i++) D[i] += D[i - 1];
for (_A = _ALast; _A != _AFirst; _C[--D[_B[*_A]]] = *_A) _A--;
}
int A[10] = { 5, 0, 3, 7, 4, 1, 9, 8, 2, 6 };
char B[11] = "cdcbaadbca";
int R[10];
int main() {
int i;
radixSort(A, A + 10, B, R, 128);
for (i = 0; i < 10; i++) printf("%d %d %d\n", i, R[i], B[R[i]]);
}'구현' 카테고리의 다른 글
| Indexed Tree with template (0) | 2017.03.22 |
|---|
