【线段树区间位运算模板】3117划分数组得到最小的值之和-阿里云开发者社区

本文涉及知识点

线段树区间位运算模板

LeetCode3117. 划分数组得到最小的值之和

给你两个数组 nums 和 andValues，长度分别为 n 和 m。

数组的值等于该数组的最后一个元素。

你需要将 nums 划分为 m 个不相交的连续子数组，对于第 ith 个子数组 [li, ri]，子数组元素的按位AND运算结果等于 andValues[i]，换句话说，对所有的 1 <= i <= m，nums[li] & nums[li + 1] & … & nums[ri] == andValues[i] ，其中 & 表示按位AND运算符。

返回将 nums 划分为 m 个子数组所能得到的可能的最小子数组值之和。如果无法完成这样的划分，则返回 -1 。

示例 1：

输入： nums = [1,4,3,3,2], andValues = [0,3,3,2]

输出： 12

解释：

唯一可能的划分方法为：

[1,4] 因为 1 & 4 == 0

[3] 因为单元素子数组的按位 AND 结果就是该元素本身

[2] 因为单元素子数组的按位 AND 结果就是该元素本身

这些子数组的值之和为 4 + 3 + 3 + 2 = 12

示例 2：

输入： nums = [2,3,5,7,7,7,5], andValues = [0,7,5]

输出： 17

解释：

划分 nums 的三种方式为：

[[2,3,5],[7,7,7],[5]] 其中子数组的值之和为 5 + 7 + 5 = 17

[[2,3,5,7],[7,7],[5]] 其中子数组的值之和为 7 + 7 + 5 = 19

[[2,3,5,7,7],[7],[5]] 其中子数组的值之和为 7 + 7 + 5 = 19

子数组值之和的最小可能值为 17

示例 3：

输入： nums = [1,2,3,4], andValues = [2]

输出： -1

解释：

整个数组 nums 的按位 AND 结果为 0。由于无法将 nums 划分为单个子数组使得元素的按位 AND 结果为 2，因此返回 -1。

提示：

1 <= n == nums.length <= 10⁴

1 <= m == andValues.length <= min(n, 10)

1 <= nums[i] < 10⁵

0 <= andValues[j] < 10⁵

线段树

求区间位运算，可以用封装的模板。

滚动线段数。

pre[i] 记录将nums[0…i]划分成r-1个数组的最小值之和。

dp[i]记录将nums[0…i]划分成r个数组的最小值之和。

pre的初始值：

如果nums[0…i]的与值为andValues[0]，则值为nums[i]，否则为非法。

dp[i]的值

如果nums[x…i]的与值为andValues[r-1]，假定x∈ \in∈(left,right]。

如果r 为0，则非法；否则

代码

核心代码

template<class TSave, class TRecord >
class CRangUpdateLineTree 
{
protected:
  virtual void OnQuery(const TSave& save, const int& iSaveLeft, const int& iSaveRight) = 0;
  virtual void OnUpdate(TSave& save, const int& iSaveLeft, const int& iSaveRight, const TRecord& update) = 0;
  virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, const int& iSaveLeft, const int& iSaveRight) = 0;
  virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) = 0;
};
template<class TSave, class TRecord >
class CTreeRangeLineTree : public CRangUpdateLineTree<TSave, TRecord>
{
protected:
  struct CTreeNode
  {
    int Cnt()const { return m_iMaxIndex - m_iMinIndex + 1; }
    int m_iMinIndex;
    int m_iMaxIndex;
    TRecord record;
    TSave data;
    CTreeNode* m_lChild = nullptr, * m_rChild = nullptr;
  };
  CTreeNode* m_root;
  TSave m_tDefault;
  TRecord m_tRecordDef;
public:
  CTreeRangeLineTree(int iMinIndex, int iMaxIndex, TSave tDefault,TRecord tRecordDef) {
    m_tDefault = tDefault;
    m_tRecordDef = tRecordDef;
    m_root = CreateNode(iMinIndex, iMaxIndex);
  }
  void Update(int iLeftIndex, int iRightIndex, TRecord value)
  {
    Update(m_root, iLeftIndex, iRightIndex, value);
  }
  TSave QueryAll() {
    return m_root->data;
  }
  void Query(int leftIndex, int leftRight) {
    Query(m_root, leftIndex, leftRight);
  }
protected:
  void Query(CTreeNode* node, int iQueryLeft, int iQueryRight) {
    if ((node->m_iMinIndex >= iQueryLeft) && (node->m_iMaxIndex <= iQueryRight)) {
      this->OnQuery(node->data,node->m_iMinIndex,node->m_iMaxIndex);
      return;
    }
    if (1 == node->Cnt()) {//没有子节点
      return;
    }
    CreateChilds(node);
    Fresh(node);
    const int mid = node->m_iMinIndex + (node->m_iMaxIndex - node->m_iMinIndex) / 2;
    if (mid >= iQueryLeft) {
      Query(node->m_lChild, iQueryLeft, iQueryRight);
    }
    if (mid + 1 <= iQueryRight) {
      Query(node->m_rChild, iQueryLeft, iQueryRight);
    }
  }
  void Update(CTreeNode* node, int iOpeLeft, int iOpeRight, TRecord value)
  {
    const int& iSaveLeft = node->m_iMinIndex;
    const int& iSaveRight = node->m_iMaxIndex;
    if ((iOpeLeft <= iSaveLeft) && (iOpeRight >= iSaveRight))
    {
      this->OnUpdate(node->data, iSaveLeft, iSaveRight, value);
      this->OnUpdateRecord(node->record, value);
      return;
    }
    if (1 == node->Cnt()) {//没有子节点
      return;
    }
    CreateChilds(node);
    Fresh(node);
    const int mid = node->m_iMinIndex + (node->m_iMaxIndex - node->m_iMinIndex) / 2;
    if (mid >= iOpeLeft) {
      this->Update(node->m_lChild, iOpeLeft, iOpeRight, value);
    }
    if (mid + 1 <= iOpeRight) {
      this->Update(node->m_rChild, iOpeLeft, iOpeRight, value);
    }
    // 如果有后代，至少两个后代
    this->OnUpdateParent(node->data, node->m_lChild->data, node->m_rChild->data,node->m_iMinIndex,node->m_iMaxIndex);
  }
  void CreateChilds(CTreeNode* node) {
    if (nullptr != node->m_lChild) { return; }
    const int iSaveLeft = node->m_iMinIndex;
    const int iSaveRight = node->m_iMaxIndex;
    const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    node->m_lChild = CreateNode(iSaveLeft, mid);
    node->m_rChild = CreateNode(mid + 1, iSaveRight);
  }
  CTreeNode* CreateNode(int iMinIndex, int iMaxIndex) {
    CTreeNode* node = new CTreeNode;
    node->m_iMinIndex = iMinIndex;
    node->m_iMaxIndex = iMaxIndex;
    node->data = m_tDefault;
    node->record = m_tRecordDef;
    return node;
  }
  void Fresh(CTreeNode* node)
  {
    if (m_tRecordDef == node->record)
    {
      return;
    }
    CreateChilds(node);
    Update(node->m_lChild, node->m_lChild->m_iMinIndex, node->m_lChild->m_iMaxIndex, node->record);
    Update(node->m_rChild, node->m_rChild->m_iMinIndex, node->m_rChild->m_iMaxIndex, node->record);
    node->record = m_tRecordDef;
  }
};
template<class TSave, class TRecord >
class CVectorRangeUpdateLineTree : public CRangUpdateLineTree<TSave, TRecord>
{
public:
  CVectorRangeUpdateLineTree(int iEleSize,TSave tDefault, TRecord tRecordNull):m_iEleSize(iEleSize)
    ,m_save(iEleSize*4,tDefault), m_record(iEleSize * 4, tRecordNull){
    m_recordNull = tRecordNull;   
  }
  void Update(int iLeftIndex, int iRightIndex, TRecord value)
  {
    Update(1, 0, m_iEleSize - 1, iLeftIndex, iRightIndex, value);
  }
  void Query(int leftIndex, int rightIndex) {
    Query(1, 0, m_iEleSize - 1, leftIndex, rightIndex);
  }
  //void Init() {
  //  Init(1, 0, m_iEleSize - 1);
  //}
  TSave QueryAll() {
    return m_save[1];
  }
  void swap(CVectorRangeUpdateLineTree<TSave, TRecord>& other) {
    m_save.swap(other.m_save);
    m_record.swap(other.m_record);
    std::swap(m_recordNull, other.m_recordNull);
    assert(m_iEleSize == other.m_iEleSize);
  }
protected:
  //void Init(int iNodeNO, int iSaveLeft, int iSaveRight)
  //{
  //  if (iSaveLeft == iSaveRight) {
  //    this->OnInit(m_save[iNodeNO], iSaveLeft);
  //    return;
  //  }
  //  const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
  //  Init(iNodeNO * 2, iSaveLeft, mid);
  //  Init(iNodeNO * 2 + 1, mid + 1, iSaveRight);
  //  this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight);
  //}
  void Query(int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight) {
    if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {
      this->OnQuery(m_save[iNodeNO],iSaveLeft,iSaveRight);
      return;
    }
    if (iSaveLeft == iSaveRight) {//没有子节点
      return;
    }
    Fresh(iNodeNO, iSaveLeft, iSaveRight);
    const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (mid >= iQueryLeft) {
      Query(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight);
    }
    if (mid + 1 <= iQueryRight) {
      Query(iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight);
    }
  }
  void Update(int iNode, int iSaveLeft, int iSaveRight, int iOpeLeft, int iOpeRight, TRecord value)
  {
    if ((iOpeLeft <= iSaveLeft) && (iOpeRight >= iSaveRight))
    {
      this->OnUpdate(m_save[iNode], iSaveLeft, iSaveRight, value);
      this->OnUpdateRecord(m_record[iNode], value);
      return;
    }
    if (iSaveLeft == iSaveRight) {
      return;//没有子节点
    }
    Fresh(iNode, iSaveLeft, iSaveRight);
    const int iMid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (iMid >= iOpeLeft)
    {
      Update(iNode * 2, iSaveLeft, iMid, iOpeLeft, iOpeRight, value);
    }
    if (iMid + 1 <= iOpeRight)
    {
      Update(iNode * 2 + 1, iMid + 1, iSaveRight, iOpeLeft, iOpeRight, value);
    }
    // 如果有后代，至少两个后代
    this->OnUpdateParent(m_save[iNode], m_save[iNode * 2], m_save[iNode * 2 + 1], iSaveLeft, iSaveRight);
  }
  void Fresh(int iNode, int iDataLeft, int iDataRight)
  {
    if (m_recordNull == m_record[iNode])
    {
      return;
    }
    const int iMid = iDataLeft + (iDataRight - iDataLeft) / 2;
    Update(iNode * 2, iDataLeft, iMid, iDataLeft, iMid, m_record[iNode]);
    Update(iNode * 2 + 1, iMid + 1, iDataRight, iMid + 1, iDataRight, m_record[iNode]);
    m_record[iNode] = m_recordNull;
  }
  vector<TSave> m_save;
  vector<TRecord> m_record;
  TRecord m_recordNull;
  const int m_iEleSize;
};
template<class TSave = int , class TRecord = int >
class CMyLineTree : public CVectorRangeUpdateLineTree<TSave, TRecord>
{
public:
  CMyLineTree(int iSize,int iNotMay) :CVectorRangeUpdateLineTree<TSave, TRecord>(iSize,iNotMay,iNotMay){
  }
  void Query(int leftIndex, int leftRight) {
    m_iQuery = CVectorRangeUpdateLineTree<TSave, TRecord>::m_recordNull;
    CVectorRangeUpdateLineTree<TSave, TRecord>::Query(leftIndex, leftRight);
  }
  int m_iQuery;
protected:
  virtual void OnQuery(const TSave& save, const int& iSaveLeft, const int& iSaveRight)  {
    m_iQuery = min(m_iQuery, save);
  }
  virtual void OnUpdate(TSave& save, const int& iSaveLeft, const int& iSaveRight, const TRecord& update) {
    save = min(save,update);
  }
  virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, const int& iSaveLeft, const int& iSaveRight) {
    par = min(left, r);
  }
  virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) {
    old = min(newRecord,old);
  }
};
class Solution {
public:
  int minimumValueSum(vector<int>& nums, const vector<int>& andValues) {
    vector<vector<pair<int, int>>> vNumIndex(nums.size());
    for (int i = 0; i < nums.size(); i++) {
      if (i) {
        for (const auto& [preNum, preIndex] : vNumIndex[i - 1]) {
          const int iNew = preNum & nums[i];
          if (vNumIndex[i].empty() || (vNumIndex[i].back().first != iNew)) {
            vNumIndex[i].emplace_back(make_pair(iNew, preIndex));
          }
          else {
            vNumIndex[i].back().second = preIndex;
          }
        }
      }
      if (vNumIndex[i].empty() || (vNumIndex[i].back().first != nums[i])) {
        vNumIndex[i].emplace_back(make_pair(nums[i], i));
      }
      else {
        vNumIndex[i].back().second = i;
      }
    }
    m_r = andValues.size();
    m_c = nums.size();
    CMyLineTree pre(m_c, m_iNotMay);
    for (int i = 0; i < m_c; i++) {
      if (andValues.front() == vNumIndex[i].front().first) {
        pre.Update(i, i, nums[i]);
      }
    } 
    for (int r = 1; r < m_r; r++)
    {
      CMyLineTree dp(m_c, m_iNotMay);
      for (int cur = 1; cur < m_c; cur++)
      {
        for (int j = vNumIndex[cur].size() - 1; j >= 0; j--) {
          if (andValues[r] == vNumIndex[cur][j].first) {
            const int left = j ? vNumIndex[cur][j - 1].second : -1;
            const int r = vNumIndex[cur][j].second;
            if (0 == r) { continue; }
            pre.Query(max(0,left), r-1);
            dp.Update(cur, cur, pre.m_iQuery + nums[cur]);
            break;
          }
        }
      }
      pre.swap(dp);
    } 
    pre.Query(m_c-1,m_c-1);
    return (pre.m_iQuery >= 1'000'000) ? -1 : pre.m_iQuery;
  }
  int m_r, m_c;
  const int m_iNotMay = 1'000'000'000;
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  vector<int>  nums, andValues;
  int k;
  {
    Solution sln;
    nums = { 1, 9, 8, 8 }, andValues = { 1,8 };
    auto res = sln.minimumValueSum(nums, andValues);
    Assert(9, res);
  }
  {
    Solution sln;
    nums = { 1, 3, 2, 4, 7, 5, 3 }, andValues = { 0, 5, 3 };
    auto res = sln.minimumValueSum(nums, andValues);
    Assert(12, res);
  }
  {
    Solution sln;
    nums = { 1, 4, 3, 3, 2 }, andValues = { 0, 3, 3, 2 };
    auto res = sln.minimumValueSum(nums, andValues);
    Assert(12, res);
  }
  //vector<int>  nums = { 3,6,9 };
  //int k;
  //
  //{
  //  Solution sln;
  //  nums = { 3,6,9 }, k = 3;
  //  auto res = sln.findKthSmallest(nums, k);
  //  Assert(9LL, res);
  //}
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。

【线段树区间位运算模板】3117划分数组得到最小的值之和

本文涉及知识点

LeetCode3117. 划分数组得到最小的值之和

线段树

代码

核心代码

测试用例

扩展阅读

视频课程

相关下载

测试环境

热门文章

最新文章

相关电子书

【线段树 区间位运算模板】3117划分数组得到最小的值之和

本文涉及知识点

LeetCode3117. 划分数组得到最小的值之和

线段树

代码

核心代码

测试用例

扩展阅读

视频课程

相关下载

测试环境

热门文章

最新文章

相关电子书

【线段树区间位运算模板】3117划分数组得到最小的值之和