
javascriptで累積和を解く
2022-02-278 min read
目次
概要
javascriptで累積和を実装した際のメモです。
累積和について
あるデータ配列内の特定の区間の中での件数の合計値を算出する際、 愚直にカウントするのではなく、 あらかじめ初項から現在の項までの合計値を計算しておくという前処理を加える事で、より高速で計算を行うことができます。
特にデータに対してたくさんのクエリが発生する場合に効果を発揮します。
例
例えば
A = [1,3,5,9,11,13,15,17,19,21]
と定義された配列の中でi
が3
〜6
の区間の合計値を求めたい場合、通常のカウント方法であれば
ans = A[3] + A[4] + A[5] + A[6]
// つまり
9 + 11 + 13 + 15 = 48
と求めると思います。
累積和の場合は、この配列について初項から現在の項までの合計値を計算するという前処理を行います。
A = [1,3,5,9,11,13,15,17,19,21]
↓
S = [A[0], A[0] + A[1], A[0] + A[1] + A[2] ... ]
// つまり
S = [1,4,9,18,29,42,57,74,93,114]
この前処理で生成したデータを利用することで、
i
が3
〜6
の区間の合計値を求めたい場合、
ans = A['区間終わり'] - A['区間始まり']
// つまり
ans = A[6] - A[2]
// つまり
57 - 9 = 48
とすることで、計算を単純にすることができます。
さらに、同じデータ配列に対して、
「i
が4
〜7
」、「i
が1
〜3
」、「i
が2
〜10
」....
と問い合わせが増えるほど効果が増えていきます。
実装
コード
let data = [1,3,5,9,11,13,15,17,19,21]
let sums = new Array(data.length).fill(0)
sums[0] = data[0]
for (let i = 1; i < data.length; i++) {
sums[i] = data[i] + sums[i - 1]
}
// 課題
let query = [
[3,6],
[1,6],
[2,6],
[5,9],
[2,4],
[3,8],
].forEach(e => {
let [l, r] = e
console.log(sums[r] - sums[l - 1])
})
結果
48
56
53
85
25
84
参考にしたサイト
Recommends
javascriptで累積和を解く
2022-02-27
JSで動的計画法を利用して部分和問題を解く
2022-02-20
NestJSアプリケーションをwebpackでBundle
2022-02-20
JavaScriptで優先度付きキューを実装する
2021-08-01
next_permutationをJSで実装する
2021-07-22
JSで32ビット符号付き整数に対してのビット演算でハマった
2021-02-17
JSでIPアドレスがサブネットマスクで指定した範囲内にあるか判定する
2021-02-16
プログラムの数値計算で発生する誤差の種類 丸め誤差・打ち切り誤差・桁落ち
2021-02-09
JSでサブネットマスクの計算
2021-02-04
Typescriptに入門した
2021-01-04
Vue/Nuxt.js 触ってた人が Next.js に入門する
2021-01-03
JavaScriptの配列ショートハンド (AtCoder用)
2020-07-05
JavaScriptで幅優先探索 (bfs) を実装する
2020-01-13
JavaScript で bit全探索
2019-06-10
深さ優先探索アルゴリズムを実装 部分和問題を解く
2018-12-25
New Posts
[AWS CDK]ECS FargateでNestJSで作成したRESTfull APIデ...
2022-05-24
[AWS CDK]S3 CloudFront OAI Route53 構成 で NextJ...
2022-05-23
[CDK]SNS+SQS+DynamoDBでBounceとComplaint情報を収集する...
2022-04-11
[AmazonSES] node.js と ejs を利用してEメールを送信する
2022-04-09
GatsbyからNext.jsへのサイト移行
2022-04-04
[AWS CDK] Lambda で S3 オブジェクトを読み書きするStackの構築
2022-03-18
[AWS CDK] S3 + CloudFrontの構築とOriginAccessIden...
2022-03-09
[AWS CDK] Bastion(踏み台)構築。SSMとEC2InstanceConne...
2022-03-06
[AWS CDK] Cognito を構築
2022-03-04
AWS CDK v2 でVPC上にAPI Gateway + Lambda + RDS +...
2022-02-28
javascriptで累積和を解く
2022-02-27
AWS Amplify で monorepo を導入し 単一リポジトリで複数プロジェクトを...
2022-02-25
AWS CDK v2 で Lambda関数のデプロイ
2022-02-23
NextJSでDevToysのようなものを作成した
2022-02-22
JSで動的計画法を利用して部分和問題を解く
2022-02-20
Hot posts!
Proxy環境下でcurlを実行する
2019-12-07
OpenCVのMatのタイプ一覧表
2018-11-25
Macでも利用できるDBクライアント MySQL PostgreSQL Oracle など
2019-12-21
TablePlusを使ってみる。シンプルでモダンなSQLクライアントツール
2018-09-30
DBクライアントツールはDBeaverをおすすめしたい
2021-03-08
AWS S3のアクセスキーIDとシークレットアクセスキーの取得 作業用ユーザを作成
2019-06-12
AtCoderで初めて色がつくまでの話(茶色) レートが中々上がらなかった原因
2018-11-25
CentOS8でEPELとPowerToolsリポジトリの有効化
2020-11-30
Macでターミナルからポートスキャンを行う方法。
2018-12-09
Python + OpenCVのfillConvexPolyで複雑なポリゴンを描画する
2018-11-27
Date
▶︎
2022 年 (23)
▶︎
2021 年 (40)
▶︎
2020 年 (30)
▶︎
2019 年 (90)
▶︎
2018 年 (89)
▶︎
2017 年 (1)
Tags
Author