怎么自己搭建一个博客网站,在线做gif图网站,聊城 网站建设,许昌网站建设汉狮怎么样前言
看这篇文章前我建议你们先看这个视频还有这个视频#xff0c;不然你们可能看不懂。
一、树状数组的核心思想与本质
核心思想#xff1a;树状数组#xff08;Fenwick Tree#xff09;是一种用于高效处理前缀和查询和单点更新的数据结构。 本质#xff1a;通过二进…前言
看这篇文章前我建议你们先看这个视频还有这个视频不然你们可能看不懂。
一、树状数组的核心思想与本质
核心思想树状数组Fenwick Tree是一种用于高效处理前缀和查询和单点更新的数据结构。 本质通过二进制索引和树形结构将前缀和的计算复杂度从
O(n) 优化到 O(logn)。
二、树状数组的基本操作 初始化 初始化一个大小为 n 的数组所有元素初始值为 0。 单点更新 更新某个位置的值并维护树状数组的结构。 前缀和查询 查询从第一个元素到某个位置的前缀和。 区间和查询 查询某个区间的和。
三、树状数组的应用场景
动态前缀和查询
实时查询数组的前缀和支持单点更新。
示例LeetCode 307. 区域和检索 - 数组可修改。
逆序对计数
使用树状数组统计数组中逆序对的数量。
示例LeetCode 493. 翻转对。
区间更新与单点查询
通过差分数组和树状数组实现区间更新和单点查询。
示例LeetCode 370. 区间加法。
二维树状数组
处理二维数组的前缀和查询和单点更新。
示例LeetCode 308. 二维区域和检索 - 可变。
四、树状数组的复杂度分析 时间复杂度 单点更新 O(logn)。
前缀和查询 O(logn)。
区间和查询 O(logn)。
空间复杂度 存储树状数组 O(n)。
五、树状数组的优化技巧 差分数组 通过差分数组实现区间更新和单点查询。 离散化 在数据范围较大时使用离散化减少树状数组的大小。 多维扩展 将树状数组扩展到二维或更高维度处理多维数组的前缀和查询和单点更新。
六、常见误区与调试技巧 误区一树状数组适用于所有区间查询问题 澄清树状数组适用于前缀和查询和单点更新对于复杂的区间查询问题可能需要其他数据结构如线段树。 误区二树状数组的初始化复杂度高 澄清树状数组的初始化复杂度为 O(nlogn)但可以通过线性初始化优化到 O(n)。 调试方法 打印树状数组在每次操作后输出树状数组的内容检查是否正确。
可视化树结构手动画出树状数组的结构模拟操作过程。
七、代码模版
单点更新
例题 【模板】树状数组 1
#includeiostream
#includevector
using namespace std;templateclass T
class FenwickTree {
private:vectorTm_tree;int lowbit(int x);
public:FenwickTree(int n):m_tree(n1,0){}void update(int idx,T val);T query(int idx);T query(int l, int r);
};templateclass T
int FenwickTreeT::lowbit(int x) {return x (-x);
}templateclass T
void FenwickTreeT::update(int idx, T val) {int n (int)m_tree.size();while (idx n) {m_tree[idx] val;idx lowbit(idx);}
}templateclass T
T FenwickTreeT::query(int idx) {T sum 0;while (idx 0) {sum m_tree[idx];idx - lowbit(idx);}return sum;
}templateclass T
T FenwickTreeT::query(int l, int r) {return query(r) - query(l - 1);
}int main() {int n, m;cin n m;FenwickTreeint ft(n);for (int i 1; i n; i) {int x;cin x;ft.update(i, x);}while (m--) {int z, x, y;cin z x y;if (z 1) {ft.update(x, y);}else {int sum ft.query(x, y);cout sum endl;}}return 0;
}
区间更新
例题 【模板】树状数组
#includeiostream
#includevector
using namespace std;templateclass T
class FenwickTree {
private:vectorTm_tree;int lowBit(int idx);void update(int idx, T val);T query(int idx);T query(int l, int r);
public:FenwickTree(int n):m_tree(n2,0){}void updateInterval(int l, int r, T val);T queryIndex(int idx);
};templateclass T
int FenwickTreeT::lowBit(int idx) {return idx -idx;
}templateclass T
void FenwickTreeT::update(int idx, T val) {int n (int)m_tree.size();while (idx n) {m_tree[idx] val;idx lowBit(idx);}
}templateclass T
T FenwickTreeT::query(int idx) {T sum 0;while (idx 0) {sum m_tree[idx];idx - lowBit(idx);}return sum;
}templateclass T
T FenwickTreeT::query(int l, int r) {return query(r) - query(l - 1);
}templateclass T
void FenwickTreeT::updateInterval(int l, int r, T val) {update(l, val);update(r 1, -val);
}templateclass T
T FenwickTreeT::queryIndex(int idx) {return query(idx);
}int main() {int n, m;cin n m;FenwickTreeintft(n);for (int i 1; i n; i) {int a;cin a;ft.updateInterval(i, i, a);}while (m--) {int opt;cin opt;if (opt 1) {int l, r, x;cin l r x;ft.updateInterval(l, r, x);}else {int k;cin k;cout ft.queryIndex(k) endl;}}return 0;
}八、经典例题
排序
#includeiostream
#includevector
using namespace std;templateclass T
class FenwickTree {
private:vectorTm_tree;int lowBit(int idx);
public:FenwickTree(int n):m_tree(n1,0){}void update(int idx, T val);T query(int idx);T query(int l, int r);
};templateclass T
int FenwickTreeT::lowBit(int idx) {return idx -idx;
}templateclass T
void FenwickTreeT::update(int idx, T val){int n m_tree.size();while (idx n) {m_tree[idx] val;idx lowBit(idx);}
}templateclass T
T FenwickTreeT::query(int idx) {T sum 0;while (idx 0) {sum m_tree[idx];idx - lowBit(idx);}return sum;
}templateclass T
T FenwickTreeT::query(int l, int r) {return query(r) - query(l - 1);
}#define maxn 1000001
int a[maxn];int main() {int n, m;cin n;FenwickTreelong longft(maxn);for (int i 0; i n; i) {cin a[i];}long long sum 0;for (int i n - 1; i 0; i--) { //逆序遍历数组看看后面有多少个比当前这个值小的个数乘于它本身累加起来ft.update(a[i], 1);sum (long long)ft.query(a[i] - 1) * a[i]; //求1~a[i]-1元素个数}cout sum endl;return 0;
}逆序对的数量
#includeiostream
#includevector
#includealgorithm
using namespace std;templateclass T
class Dicretizer {
private:vectorTm_data;
public:void addData(T v);void process();int get(T v) const;int size() const;
};templateclass T
void DicretizerT::addData(T v) {m_data.push_back(v);
}templateclass T
void DicretizerT::process() {sort(m_data.begin(), m_data.end());int lastId 0;for (int i 1; i m_data.size(); i) {T x m_data[i];if (x ! m_data[lastId]) {m_data[lastId] x;}}while (lastId m_data.size() - 1) {m_data.pop_back();}
}templateclass T
int DicretizerT::get(T v) const {int l -1, r m_data.size();while (l 1 r) {int mid (l r) / 2;if (m_data[mid] v)r mid;else l mid;}if (r m_data.size() || m_data[r] ! v)return -1;return r;
}templateclass T
int DicretizerT::size() const {return m_data.size();
}templateclass T
class FenwickTree {
private:vectorTm_tree;int lowBit(int idx);
public:FenwickTree(int n):m_tree(n1,0){}void update(int idx, T val);T query(int idx);T query(int l, int r);
};templateclass T
int FenwickTreeT::lowBit(int idx) {return idx -idx;
}templateclass T
void FenwickTreeT::update(int idx, T val){int n m_tree.size();while (idx n) {m_tree[idx] val;idx lowBit(idx);}
}templateclass T
T FenwickTreeT::query(int idx) {T sum 0;while (idx 0) {sum m_tree[idx];idx - lowBit(idx);}return sum;
}templateclass T
T FenwickTreeT::query(int l, int r) {return query(r) - query(l - 1);
}#define maxn 1000001
int a[maxn];int main() {int n;cin n;Dicretizerintd;FenwickTreeintft(n);for (int i 0; i n; i) {cin a[i];d.addData(a[i]);}d.process(); for (int i 0; i n; i) {a[i] d.get(a[i]) 1; //树状数组的序号是从1开始利用离散化给原数组每个值标记它的序号也就是排序好它们的大小}long long sum 0;for (int i n - 1; i 0; i--) {ft.update(a[i], 1);sum ft.query(a[i] - 1); //查询1~a[i]-1的元素和他要找的是比它本身小的个数}cout sum endl;return 0;
}三元组个数
这题就是遍历到的原数组的每一个元素用左边比它小的个数乘于右边比它大的个数但是复杂度还是太高了所以还得需要离散化数组用树状数组记录比它小或大的个数
#includeiostream
#includevector
#includealgorithm
using namespace std;templateclass T
class Dicretizer {
private:vectorTm_data;
public:void addData(T v);void process();int get(T v) const;int size() const;
};templateclass T
void DicretizerT::addData(T v) {m_data.push_back(v);
}templateclass T
void DicretizerT::process() {sort(m_data.begin(), m_data.end());int lastId 0;for (int i 1; i m_data.size(); i) {T x m_data[i];if (x ! m_data[lastId]) {m_data[lastId] x;}}while (lastId m_data.size() - 1) {m_data.pop_back();}
}templateclass T
int DicretizerT::get(T v) const {int l -1, r m_data.size();while (l 1 r) {int mid (l r) / 2;if (m_data[mid] v)r mid;else l mid;}if (r m_data.size() || m_data[r] ! v)return -1;return r;
}templateclass T
int DicretizerT::size() const {return m_data.size();
}templateclass T
class FenwickTree {
private:vectorTm_tree;int lowBit(int idx);
public:FenwickTree(int n):m_tree(n1,0){}void update(int idx, T val);T query(int idx);T query(int l, int r);
};templateclass T
int FenwickTreeT::lowBit(int idx) {return idx -idx;
}templateclass T
void FenwickTreeT::update(int idx, T val){int n m_tree.size();while (idx n) {m_tree[idx] val;idx lowBit(idx);}
}templateclass T
T FenwickTreeT::query(int idx) {T sum 0;while (idx 0) {sum m_tree[idx];idx - lowBit(idx);}return sum;
}templateclass T
T FenwickTreeT::query(int l, int r) {return query(r) - query(l - 1);
}#define mod 998244353
#define maxn 1000001
int a[maxn], lt[maxn]; //lt[i]表示小于a[i]的个数int main() {int n;cin n;Dicretizerintd;FenwickTreeintft(n);for (int i 0; i n; i) {cin a[i];d.addData(a[i]);}d.process(); for (int i 0; i n; i) {a[i] d.get(a[i]) 1; //树状数组的序号是从1开始利用离散化给原数组每个值标记它的序号也就是排序好它们的大小}for (int i 0; i n; i) {ft.update(a[i], 1);lt[i] ft.query(a[i] - 1);}ft FenwickTreeint(n);long long sum 0;for (int i n - 1; i 0; i--) {ft.update(a[i], 1);int gt ft.query(a[i] 1, n); //求出比a[i]大的个数sum (long long)lt[i] * gt % mod;sum % mod; //sum这个值可能超出范围所以还要取模}cout sum endl;return 0;
}九、总结与学习建议
核心总结 树状数组是一种高效处理前缀和查询和单点更新的数据结构。
通过二进制索引和树形结构将复杂度优化到 O(logn)。
学习建议 分类刷题按问题类型集中练习如动态前缀和、逆序对计数、区间更新。
理解算法原理掌握树状数组的实现步骤和优化技巧。
手写模拟过程在纸上画出树状数组的结构模拟操作过程加深直观理解。
通过以上分析树状数组作为一种高效的数据结构在算法竞赛和实际应用中具有广泛用途。掌握其核心思想和实现技巧能够有效提升算法效率。 希望大家可以一键三连后续我们一起学习谢谢大家 文章转载自： http://www.morning.rwwdp.cn.gov.cn.rwwdp.cn http://www.morning.bnqcm.cn.gov.cn.bnqcm.cn http://www.morning.jkdtz.cn.gov.cn.jkdtz.cn http://www.morning.tndhm.cn.gov.cn.tndhm.cn http://www.morning.bpmdh.cn.gov.cn.bpmdh.cn http://www.morning.rlxg.cn.gov.cn.rlxg.cn http://www.morning.pctql.cn.gov.cn.pctql.cn http://www.morning.dhqzc.cn.gov.cn.dhqzc.cn http://www.morning.fnssm.cn.gov.cn.fnssm.cn http://www.morning.fycjx.cn.gov.cn.fycjx.cn http://www.morning.pzpj.cn.gov.cn.pzpj.cn http://www.morning.wpsfc.cn.gov.cn.wpsfc.cn http://www.morning.hdzty.cn.gov.cn.hdzty.cn http://www.morning.nbsfb.cn.gov.cn.nbsfb.cn http://www.morning.rqlqd.cn.gov.cn.rqlqd.cn http://www.morning.czrcf.cn.gov.cn.czrcf.cn http://www.morning.hbywj.cn.gov.cn.hbywj.cn http://www.morning.fesiy.com.gov.cn.fesiy.com http://www.morning.nppml.cn.gov.cn.nppml.cn http://www.morning.wwthz.cn.gov.cn.wwthz.cn http://www.morning.plqsz.cn.gov.cn.plqsz.cn http://www.morning.cpqqf.cn.gov.cn.cpqqf.cn http://www.morning.mdtfh.cn.gov.cn.mdtfh.cn http://www.morning.jkmjm.cn.gov.cn.jkmjm.cn http://www.morning.gbwfx.cn.gov.cn.gbwfx.cn http://www.morning.wmfny.cn.gov.cn.wmfny.cn http://www.morning.nkpml.cn.gov.cn.nkpml.cn http://www.morning.xrmwc.cn.gov.cn.xrmwc.cn http://www.morning.dpnhs.cn.gov.cn.dpnhs.cn http://www.morning.kmcfw.cn.gov.cn.kmcfw.cn http://www.morning.kbfzp.cn.gov.cn.kbfzp.cn http://www.morning.xqspn.cn.gov.cn.xqspn.cn http://www.morning.sryyt.cn.gov.cn.sryyt.cn http://www.morning.rycd.cn.gov.cn.rycd.cn http://www.morning.qmnjn.cn.gov.cn.qmnjn.cn http://www.morning.fkmyq.cn.gov.cn.fkmyq.cn http://www.morning.nxwk.cn.gov.cn.nxwk.cn http://www.morning.snrhg.cn.gov.cn.snrhg.cn http://www.morning.psxcr.cn.gov.cn.psxcr.cn http://www.morning.kdldx.cn.gov.cn.kdldx.cn http://www.morning.yhwmg.cn.gov.cn.yhwmg.cn http://www.morning.ljzss.cn.gov.cn.ljzss.cn http://www.morning.pgkpt.cn.gov.cn.pgkpt.cn http://www.morning.qwzpd.cn.gov.cn.qwzpd.cn http://www.morning.frpb.cn.gov.cn.frpb.cn http://www.morning.hdpcn.cn.gov.cn.hdpcn.cn http://www.morning.jrrqs.cn.gov.cn.jrrqs.cn http://www.morning.qyxwy.cn.gov.cn.qyxwy.cn http://www.morning.wwthz.cn.gov.cn.wwthz.cn http://www.morning.rbzht.cn.gov.cn.rbzht.cn http://www.morning.bmncq.cn.gov.cn.bmncq.cn http://www.morning.tcfhs.cn.gov.cn.tcfhs.cn http://www.morning.rwwdp.cn.gov.cn.rwwdp.cn http://www.morning.cyyhy.cn.gov.cn.cyyhy.cn http://www.morning.zlhbg.cn.gov.cn.zlhbg.cn http://www.morning.qnbzs.cn.gov.cn.qnbzs.cn http://www.morning.wbyqy.cn.gov.cn.wbyqy.cn http://www.morning.hsjfs.cn.gov.cn.hsjfs.cn http://www.morning.bpmtq.cn.gov.cn.bpmtq.cn http://www.morning.lcbt.cn.gov.cn.lcbt.cn http://www.morning.jnbsx.cn.gov.cn.jnbsx.cn http://www.morning.ghxzd.cn.gov.cn.ghxzd.cn http://www.morning.lfdzr.cn.gov.cn.lfdzr.cn http://www.morning.dshkp.cn.gov.cn.dshkp.cn http://www.morning.nkpls.cn.gov.cn.nkpls.cn http://www.morning.nkqnn.cn.gov.cn.nkqnn.cn http://www.morning.qjghx.cn.gov.cn.qjghx.cn http://www.morning.dmzqd.cn.gov.cn.dmzqd.cn http://www.morning.ncfky.cn.gov.cn.ncfky.cn http://www.morning.mlcnh.cn.gov.cn.mlcnh.cn http://www.morning.pccqr.cn.gov.cn.pccqr.cn http://www.morning.dqpnd.cn.gov.cn.dqpnd.cn http://www.morning.drcnn.cn.gov.cn.drcnn.cn http://www.morning.lwhsp.cn.gov.cn.lwhsp.cn http://www.morning.dhnqt.cn.gov.cn.dhnqt.cn http://www.morning.rcjyc.cn.gov.cn.rcjyc.cn http://www.morning.ymmjx.cn.gov.cn.ymmjx.cn http://www.morning.phjyb.cn.gov.cn.phjyb.cn http://www.morning.hcwlq.cn.gov.cn.hcwlq.cn http://www.morning.oioini.com.gov.cn.oioini.com
